为什么我不习惯用递归，这方面我应该怎么加强？

递归

苦恼

代码

81 条回复 • 1970-01-01 08:00:00 +08:00

1

messense

2013-05-08 19:54:59 +08:00

人理解迭代，神理解递归。。。实在想不明白就这么安慰自己好了。

2

leiz

2013-05-08 20:02:43 +08:00

递归说白了就是数学归纳法

3

chemzqm

2013-05-08 20:06:15 +08:00

不用递归会对你写出好代码有多大影响？

4

darasion

2013-05-08 20:07:17 +08:00

@leiz 说的对。就当是用数学归纳法证明一道数学题。

5

holmesabc

2013-05-08 20:07:35 +08:00

其实把入与出的条件想清楚，就好理解了

6

iloahz

2013-05-08 20:15:25 +08:00

我觉得自己跟着递归的程序跑一跑挺好的，就是在大脑里一条一条的执行语句，比如hanoi

7

Cadina

2013-05-08 20:28:33 +08:00

1

不要尝试理解递归，理解数学归纳法或循环不变式

8

YUCOAT

2013-05-08 20:33:41 +08:00

最近我在研究红黑树，感觉红黑树实现起来好复杂。。
后来想想其实不算复杂，之所以觉的复杂，无非是因为自己没有理解透。所以啊，想办法先理解透了再说吧。

9

detailyang

2013-05-08 20:43:53 +08:00

要理解递归,首先要理解递归 = =,我也被搞死,二叉树,深度优先 = =

10

solesschong

2013-05-08 20:44:50 +08:00

做纯程序员才用到递归。实在不喜欢递归可以去做前台，做应用。

11

Golevka

2013-05-08 20:58:10 +08:00

Go functional yourself, Webvolutionaries!

12

wodemyworld

2013-05-08 21:02:51 +08:00

1

盗梦空间就是个递归系统，最后很可能回到现实了还return呢，或者在某一层梦境中丢了陀螺，结果出不来了
如果不是十分自信，就别用递归了，耗栈区资源，切换上下文频繁，也没多大收益，现在基本没人用专门的递归机器（硬件）了，所以能转换成for循环的就别用这货了。。。。

13

alexrezit

2013-05-08 21:09:26 +08:00

我觉得递归理解起来更简单啊.
用循环总是搞错次数, 用递归就从来不会.

14

liwei

2013-05-08 21:09:52 +08:00

推荐你看一下SICP

http://mitpress.mit.edu/sicp/full-text/book/book.html

15

xatest

2013-05-08 21:27:43 +08:00

3

从机器执行程序的角度来说迭代的效率肯定高于递归，因为递归在执行时需要函数嵌套好多层，对函数栈的消耗相当大，看上去就如同一段缩进了很多层的代码。所以LZ能优先用迭代而不是递归的话，反而是一个优势啊，我往往就想不到，LZ没什么好苦恼的。
但是从人理解的容易程度上讲，递归更容易理解吧。试想一个典型的递归结构，就是文件系统里的目录，每个目录里可能还有目录。如果要写一个函数，列出文件系统上所有目录和文件，最容易想到的算法是什么？首先写一个函数，列出当前层的所有目录和文件（类似ls命令），如果列出的是目录，再调用自身，不就解决了。

16

glume

2013-05-08 21:35:15 +08:00

碰见类似的问题。曾写帖子“回复”代码，一层回复一层，如果不停的回复前面的回复，嵌套起来压力很大。

17

youlil

2013-05-08 22:41:44 +08:00

@leiz 递归和数学归纳法是正反的区别

18

swulling

2013-05-08 22:45:41 +08:00

生产环境老板要写个阶乘，谁要写个递归版本的，直接被开掉

19

Golevka

2013-05-08 23:12:26 +08:00

@swulling
sub factorial {
reduce {$a * $b} 1, 1 .. $_[0];
}
ML与Haskell里也有fold类似物, 但是fold也是递归定义的.

20

davepkxxx

2013-05-08 23:33:56 +08:00

递归我能不用就不用。

21

plan9

2013-05-08 23:40:20 +08:00

@davepkxxx 记得某本书里写过：我的程序员要是用递归去计算阶乘，我宁愿换人。

22

nsa

2013-05-08 23:49:43 +08:00

@plan9 代码大全。。。

23

xavierskip

2013-05-08 23:55:57 +08:00

1

递归的规则很简单
1，需要调用本身
2，有个结束的条件

把一个大问题转化为同样的小问题，递归不就是就是不停的乘以比他大1的数吗。 n*f(n+1)

为了好判断终止条件，我们换成换成 n*f(n-1)

在函数内部设定个终止条件

def f(n):
____if n == 1:
________return 1

这个函数内部的n显然不再是外面带进去的那个n了，每个函数中都有一个不一样的n。

def f(n):
____if n == 1:
________return 1
____else:
________return n*f(n-1)

再了解递归可以去看看点稍微复杂点的例子，像二分法求平方根，快速排序。

24

nsa

2013-05-09 00:01:21 +08:00

孩子买书去学吧，推荐莫绍揆的《递归论》

25

oyasmi

2013-05-09 00:07:50 +08:00

@liwei 嗯，同样推荐SICP，很强调递归的说，尤其习题要做一下。

26

lululau

2013-05-09 00:15:12 +08:00

@xatest 同意，我也觉得递归是对一个问题的更容易的解决方式，同样也是更没运行效率的一种解决方式

27

sectic

2013-05-09 00:21:26 +08:00 via iPhone

递归可以写阶乘，不慢。
迭代就是加了一个计数参数的尾递归。
递归有些时候不用就搞不出来。

28

sectic

2013-05-09 00:22:20 +08:00 via iPhone

吐个血槽，scheme 读输入都是拿递归

29

monkeylyf

2013-05-09 01:08:18 +08:00

写一点functional programming的东西 scala, haskell 不想递归也得递归

30

lldong

2013-05-09 01:30:22 +08:00

Programming With Nothing
http://codon.com/programming-with-nothing
http://rubymanor.org/3/videos/programming_with_nothing/

31

Ricepig

2013-05-09 05:06:46 +08:00

可以学学分形几何嘛，娃哈哈哈哈，自相似

32

csslayer

2013-05-09 05:11:29 +08:00

写 functional programming，把循环想成尾递归

33

davepkxxx

2013-05-09 09:19:40 +08:00

我记得我之前学习Scala，因为其不支持break而苦恼，结果Google Groups上的人推荐我用递归代替循环……

34

williamx

2013-05-09 09:25:53 +08:00

说明你是一个比较勤快的人---->当你变懒了之后，你就会想用递归等等----当然，优秀的程序员都是“懒”的。

35

fooCoder

2013-05-09 09:57:53 +08:00

@solesschong 什么是纯的程序员。。。

36

solesschong

2013-05-09 10:09:39 +08:00 via iPad

@fooCoder 就是真正工作的时候很可能用不到。除非写很理论的东西

37

tyzc

2013-05-09 10:13:37 +08:00

@xatest 赞同。递归简单理解就是函数调用函数，不过调用的函数是自己而已。

38

fooCoder

2013-05-09 10:22:34 +08:00

@solesschong 也就是说你的意思是“纯的程序员”，就是搞理论的？

39

celadevra

2013-05-09 10:30:24 +08:00

1

可以跟一遍这个课程：https://class.coursera.org/proglang-2012-001/class/index
虽然只是个大三大四的课，其中大部分 SML 和 Racket 写的作业都要用到递归，做完一遍就差不多养成习惯了。

40

primer

2013-05-09 10:46:55 +08:00

1

这个我觉得主要靠练习，我刚开始接触递归的时候，也是像楼主一样搞不懂。后来多想想，多练习，也发现没什么难的。
楼主可以从栈这方面理解，递归说白了就是不断的压栈呀，出栈...

41

skywalker

2013-05-09 11:08:21 +08:00

用一段Haskell就习惯了，其实更多是一种思维训练，如果找出问题的规律，将其分解为更小规模的问题.

42

zhujinliang

2013-05-09 11:10:26 +08:00

业余玩单片机的表示没法用递归，内存按字节数，一搞递归要吃多少内存啊

43

xdeng

2013-05-09 11:14:36 +08:00

递归很好么？？？小心栈溢出

44

zhicheng

2013-05-09 11:15:58 +08:00

一句话，学并且用 Clojure 。在类C的语言里，不要使用递归。

45

justfly

OP

2013-05-09 11:23:57 +08:00

@leiz 经你一说觉得确实是这样，我再温习一遍数学归纳法

46

justfly

OP

2013-05-09 11:26:14 +08:00

@xavierskip

恩，以后递归的问题从这两点出发去考虑

47

oldcai

2013-05-09 11:27:28 +08:00

@xdeng 同忧心。

48

justfly

OP

2013-05-09 11:30:59 +08:00

@zhujinliang 当然单片机这种寸土寸金的地方就不考虑这些啦

49

skywalker

2013-05-09 11:31:14 +08:00

@xdeng 用尾递归

50

Mutoo

2013-05-09 11:39:14 +08:00

1

计算机上的递归实际上就是栈+循环而已。

51

onesuper

2013-05-09 12:20:13 +08:00

http://vivid.chengyichao.info/

52

skywalker

2013-05-09 12:59:50 +08:00

@onesuper 牛！太好了

53

Cadina

2013-05-09 13:06:37 +08:00

1

@zhujinliang 说递归有效率问题的，可以看下尾递归优化

54

solesschong

2013-05-09 14:08:12 +08:00 via iPad

@fooCoder 是。我不和你说了，再说没钱了。刚注册

55

yexiang841

2013-05-09 15:42:17 +08:00

生产环境下谁用递归开除谁，无二话。

56

zhujinliang

2013-05-09 18:10:02 +08:00

@Cadina 谢谢，明天早上研究一下

57

kylefeng

2013-05-09 18:36:55 +08:00

去看《The Little Schemer》吧。

58

diligence24

2013-05-09 18:52:42 +08:00

我觉得写递归要想清楚什么时候return。具体的问题你可以debug，不过切记测试数据要简单却不失代表性。不然不会单步到找不着北的。。。

59

seeker

2013-05-09 20:49:23 +08:00

学一门函数式语言。lisp,ML,haskell自动就会了

60

tioover

2013-05-10 00:25:42 +08:00 via Android

我不太习惯用迭代，这方面我该做什么加强。

61

Idiosyncratic

2013-05-10 13:14:29 +08:00

@Cadina 尾递归只能优化尾递归，又不能优化各种递归，如果是递归函数里调用两次递归(深搜二叉树)，这样还是没法优化啊。。，所以递归递归效率的确不高

62

Cadina

2013-05-10 13:54:27 +08:00

@Idiosyncratic 但是树型递归这类问题，递归产生的cost是必须的，即使不用递归也需要手动维护栈或者类似的数据结构，和递归的耗费是一样的，这就不是递归本身的性能问题了，你没有其他的选择。
所以你说的效率不高其实是算法的问题，而不是递归的问题。
引入尾递归优化的价值在于，用更抽象的代码解决问题，并且没有额外的性能消耗。

63

Idiosyncratic

2013-05-10 15:48:14 +08:00

@Cadina 尾递归只是一个编译优化而已，没你说的那么神奇吧，还是那句话，尾递归只能优化在递归函数最后调用递归的问题，而且做法就是把这样的递归改成与for循环类似的样式；
递归的简洁、抽象是必须的，但是在实际系统里它的效率问题也很明显。你认为递归和手动维护这样的耗费是一样的，这个我觉的不准确，递归的性能消耗有这么几个方面：
1、它每次都需要把所有的局部变量压栈，不管这个局部变量还要不要用；
2、它是一个函数一个函数为单位进行调用的，调用函数是有消耗；
以上两个方面在迭代次数不大的时候其实不是啥问题，但是次数一多就会成为问题了；
而递归需要的消耗，在for循环一类的迭代里完全可以避免。
就拿深搜来说，一般用for循环迭代之前，都会先开一个容器(数组，字典都行)，把所有节点的初始状态保存进去，然后每遍历一个节点修改容器里相应的元素内容，很多在递归里需要的消耗（压栈，出栈，跳转等）在这就没有了；

尾递归优化当然是很好的东东，但是目前应该还没有可以把所有递归都优化的很好的法子；所以我感觉递归的效率还是有些低。

当然，递归最大的问题还是它很容易把栈给挤爆。。。

64

Golevka

2013-05-10 16:25:22 +08:00

@Idiosyncratic "一般用for循环迭代之前，都会先开一个容器(数组，字典都行)，把所有节点的初始状态保存进去，然后每遍历一个节点修改容器里相应的元素内容"

这做法整个一杯具啊. 比如考虑遍历一个N个节点的二叉树, 用DFS递归遍历的渐进空间复杂度只有O(logN), 开一个容器然后迭代的空间复杂度总是O(n). 如果要DFS的二叉树是平衡的那么递归的空间开销则可以直接忽略了. 遍历一颗1T节点的平衡二叉树所需要的堆栈桢也不会超过100个单位. 你有1T内存还拿不出100个函数调用的栈桢么?

递归的空间消耗是由递归的深度和tail call共同决定的. 在能保证递归深度的渐进增长率是可接受的情况下直接递归也不会有什么问题, 尤其是递归代码显然更简洁且易维护的情况下.

65

unionx

2013-05-10 16:33:18 +08:00

递归我能不用就不用+1

66

Golevka

2013-05-10 16:37:23 +08:00

@unionx 发现野生帝老师

67

Idiosyncratic

2013-05-10 20:14:18 +08:00

@Golevka 大哥，我觉得你混淆了好多情况啊。。：
1、时间复杂度：一个算法的空间复杂度(Space Complexity)S(n)定义为该算法所耗费的存储空间，是对一个算法在运行过程中临时占用存储空间大小的量度；递归算法在结束全所有节点都不得释放，O(logN)能存的下O（N）级的内容？不论是啥样的dfs算法，需要的空间起码是O（n）的，因为是遍历n个节点，起码记录节点遍历没有的标记符就要有N个； O(logN)那是完全二叉树的高度，是完全二叉树的递归层数，可以说是一个特例而已，也只能说是和空间相关。

2、dfs的遍历方式是给定的，只要照着dfs做，除非故意找茬（故意开个超大内存啥的），算法的空间时间复杂度都是一样；

3、栈空间和内存空间不是一回事，vc6的C语言编译器默认的栈空间只有1M(其他环境相差不大，反正默认的都不大)，不然大家怎么会天天说递归容易爆栈？想要扩大栈空间只有在程序运行前在IDE或是命令行里指定，就是说程序本身决定不了，这样的递归，除非你每次运行前都先估摸这一下要用多少栈空间，不然应付各种规模数据的时候总会有爆掉的一天；相比来说，可以在内村里手动开辟的法子显然更好；

4、有一个很重要的问题，我再重复一下，dfs的空间、时间复杂度，在算法上是一样的，不是说递归层数变少，空间就变小了；层数变少，只是要存的局部变量就是变少了，但是用其他方法实现的时候完全可以不存储那些局部变量：
int a(){
int b;
if xx:
return;
a();
}
b要存下；

while(!xxx){
int b
&(&(
}
b不用存；

因此，在理论上时间，空间一致的情况下，递归还有各种实现上的开销，所以效率低；

PS：这句话：“都会先开一个容器(数组，字典都行)，把所有节点的初始状态保存进去”，存的就是二叉树好吧，二叉树经常这么存储，然后在每个节点元素里加上个种信息。
本来还想在写点，但是看着已经写好多了，在写下去就太烦了。。，主要是觉得你没搞懂。。。还说我的法子不对。。有些不爽。。

68

ccinls

2013-05-10 20:27:54 +08:00

递归除了让你感受到算法的奥妙的之外，基本毫无用处。况且，能不用递归，尽量不要用递归。不过这个思维过程比较有趣~
PS：我算是半吊子玩算法的。

69

Idiosyncratic

2013-05-10 20:28:28 +08:00

@Golevka 呃，一时手快，刚刚的回复打错了几个字

“1、时间复杂度” => 想打的是“1、空间复杂度”

第5行“可以说是一个特例而已，也只能说是和空间相关。” => 其实我想说的是，完全二叉树是性质很好一个种树。。

70

myrual

2013-05-10 20:36:10 +08:00 via iPhone

反复练习

71

Golevka

2013-05-10 20:45:51 +08:00

@Idiosyncratic
0. 呀, 如果度量算法空间复杂度还要算上数据本身占用的空间的话, 你能解释一下quicksort的O(logN)的空间复杂度是怎么得来的么?
1. 我前面提到的1T单位的空间是[存储]二叉树需要的空间, 而非执行递归调用所需的[栈空间];
2. 虽然某些方法能获得更好的渐进复杂度; 但这种[更好]有时只是"galactic improvments". 你认为O(logN)和O(1)有多大的差距, 在你的计算机所能承受的数据范围内?

72

Idiosyncratic

2013-05-10 21:05:15 +08:00

@Golevka
0. 空间复杂度和渐进空间复杂度嘛，你本来说渐进空间复杂度，但是却说存储了节点后的算法（我原来给的算法）的渐进空间复杂度是O（N）。而这O（N）是dfs的空间复杂度。。。
1、至于一颗1T的树。。，具体的总有trick的法子可以不用一口读这么多的，但是递归同时要存储占用更多的栈空间；具体的我没啥数据，不过我以前多一个500多M的文件夹内txt文件（随机生成的）进行单词词频统计，用递归的法子把栈挤爆过；
2、这个问题。。，和递归效率有关系吗，咱们没讨论这个吧。。

73

Golevka

2013-05-10 21:14:57 +08:00

@Idiosyncratic
0. http://en.wikipedia.org/wiki/Depth-first_search
Hint: 右侧的示意图下面有个大大的O(|V|), 并且Properties中也明确说"space complexity of this variant of DFS is only proportional to the depth limit"

1. 我之所以提到1T balanced binary tree并非强调把数据读入内存有多困难或者应该用怎样的trick分块处理, 而是强调O(logN)的增长速度很慢以至于N[非常大]时也很足够小, 在实际应用场合也是可以接受的. (一般认为log(N) in real world <= 64);

2. 同#1

74

volCANo

2013-05-10 21:27:11 +08:00

即使所有的递归能弄成尾递归，调用函数的开销也会使速度变慢。当然，如果调用函数的开销只占所有开销很小一部分的话，还是用尾递归较好，用尾递归的代码更好看，更容易理解。

75

Idiosyncratic

2013-05-10 21:33:40 +08:00

@Golevka
0、我真的被你搞糊涂了，空间复杂度是O（N）没错啊，我都说了几遍了，（V是指节点个数，和我们的N是一个意思，E是边数，无环图下E=V-1），空间复杂度和渐进空间复杂度不同。。fine，你自己琢磨一下我们帖子的对答吧，；至于wiki的话，不能忽视上下文吧：“In this case, the time is still linear in the number of expanded vertices and edges (although this number is not the same as the size of the entire graph because some vertices may be searched more than once and others not at all) but the space complexity of this variant of DFS is only proportional to the depth limit”
我就不具体翻译了，大意是 "时间依然是节点数和边数和的倍数；但是这个dfs变种算法的空间复杂度是受深度限制的"；这个算法是个变种，不记录节点是否遍历，和我提的那个不同；

1、这个，空间复杂度都是N，渐进复杂度，没错递归是O(logN),但是非递归的渐进复杂度。。。，我就不仔细解释了，一次for循环只抓一个节点。。。；
2、同#1

76

Golevka

2013-05-10 21:37:16 +08:00

@Idiosyncratic
0. 晕... 抱歉我会错意了. 我本来想说因为遍历的是tree所以可以不维护visited set的 = =
1. 前面说好的要[把所有节点的初始状态保存进去]呢, 难道这一步不需要O(|V|)的空间么

77

Golevka

2013-05-10 21:52:57 +08:00

@Idiosyncratic 好吧我知道了, 乃刚才的讨论都是针对任意图的DFS, 我只想到遍历树了

78

wy315700

2013-05-10 22:04:55 +08:00

能用循环尽量用循环递归是个坑不好调试也容易崩溃，尤其深度过大的时候容易爆栈

图灵证明过循环和递归是等价的
DFS可以无缝转换成BFS

79

Idiosyncratic

2013-05-10 22:11:52 +08:00

@Golevka 奥，这样啊。。，好像是哦。。,= =

80

Cadina

2013-05-10 22:41:26 +08:00

@volCANo 尾递归的优化就是把函数调用优化成循环。。。

81

volCANo

2013-05-12 10:37:12 +08:00

@Cadina 不是吧！？，尾递归的优化是去除爆栈的可能性，还是会产生函数调用的消耗的。