递归的优缺点
2.在树的前序，中序，后序遍历算法中，递归的实现明显要比循环简单得多。
1.递归由于是函数调用自身，而函数调用是有时间和空间的消耗的：每一次函数调用，都需要在内存栈中分配空间以保存参数、返回地址以及临时变量，而往栈中压入数据和弹出数据都需要时间。-&效率
2.递归中很多计算都是重复的，由于其本质是把一个问题分解成两个或者多个小问题，多个小问题存在相互重叠的部分，则存在重复计算，如fibonacci斐波那契数列的递归实现。-&效率
3.调用栈可能会溢出，其实每一次函数调用会在内存栈中分配空间，而每个进程的栈的容量是有限的，当调用的层次太多时，就会超出栈的容量，从而导致栈溢出。-&性能
没有更多推荐了，
不良信息举报
举报内容：
递归的优缺点
举报原因：
原文地址：
原因补充：
最多只允许输入30个字
加入CSDN，享受更精准的内容推荐，与500万程序员共同成长！为什么我不习惯用递归，这方面我应该怎么加强？
19:53:55 +08:00用 iPhone 发布 · 10983 次点击
这个问题很苦恼。比如说我想计算一个数的阶乘 n! 我首先想到的是用for循环一个一个的乘，根本想不到递归的方法。当然这只是一个例子，当初学数据结构，二叉树遍历代码很简单，但因为是递归的，就觉得理解不透的感觉，汉诺塔那个递归算法也是记不住。太苦恼了虽然所有递归理论来说都可以用普通方法代替，但是递归代码清晰易懂的优势也很大，所以请不要说难理解就别深究这样的话。请各位v2exer解惑，感谢！
81 回复 &| &直到
08:00:00 +08:00
& & 19:54:59 +08:00
人理解迭代，神理解递归。。。实在想不明白就这么安慰自己好了。
& & 20:02:43 +08:00
递归说白了就是数学归纳法
& & 20:06:15 +08:00
不用递归会对你写出好代码有多大影响？
& & 20:07:17 +08:00
@ 说的对。就当是用数学归纳法证明一道数学题。
& & 20:07:35 +08:00
其实把入与出的条件想清楚，就好理解了
& & 20:15:25 +08:00
我觉得自己跟着递归的程序跑一跑挺好的，就是在大脑里一条一条的执行语句，比如hanoi
& & 20:28:33 +08:00
不要尝试理解递归，理解数学归纳法或循环不变式
& & 20:33:41 +08:00
最近我在研究红黑树，感觉红黑树实现起来好复杂。。
后来想想其实不算复杂，之所以觉的复杂，无非是因为自己没有理解透。所以啊，想办法先理解透了再说吧。
& & 20:43:53 +08:00
要理解递归,首先要理解递归 = =,我也被搞死,二叉树,深度优先 = =
& & 20:44:50 +08:00
做纯程序员才用到递归。实在不喜欢递归可以去做前台，做应用。
& & 20:58:10 +08:00
Go functional yourself, Webvolutionaries!
& & 21:02:51 +08:00
盗梦空间就是个递归系统，最后很可能回到现实了还return呢，或者在某一层梦境中丢了陀螺，结果出不来了
如果不是十分自信，就别用递归了，耗栈区资源，切换上下文频繁，也没多大收益，现在基本没人用专门的递归机器（硬件）了，所以能转换成for循环的就别用这货了。。。。
& & 21:09:26 +08:00
我觉得递归理解起来更简单啊.
用循环总是搞错次数, 用递归就从来不会.
& & 21:09:52 +08:00
推荐你看一下SICP
& & 21:27:43 +08:00
从机器执行程序的角度来说迭代的效率肯定高于递归，因为递归在执行时需要函数嵌套好多层，对函数栈的消耗相当大，看上去就如同一段缩进了很多层的代码。所以LZ能优先用迭代而不是递归的话，反而是一个优势啊，我往往就想不到，LZ没什么好苦恼的。
但是从人理解的容易程度上讲，递归更容易理解吧。试想一个典型的递归结构，就是文件系统里的目录，每个目录里可能还有目录。如果要写一个函数，列出文件系统上所有目录和文件，最容易想到的算法是什么？首先写一个函数，列出当前层的所有目录和文件（类似ls命令），如果列出的是目录，再调用自身，不就解决了。
& & 21:35:15 +08:00
碰见类似的问题。曾写帖子“回复”代码，一层回复一层，如果不停的回复前面的回复，嵌套起来压力很大。
& & 22:41:44 +08:00
@ 递归和数学归纳法是正反的区别
& & 22:45:41 +08:00
生产环境老板要写个阶乘，谁要写个递归版本的，直接被开掉
& & 23:12:26 +08:00
sub factorial {
reduce {$a * $b} 1, 1 .. $_[0];
}
ML与Haskell里也有fold类似物, 但是fold也是递归定义的.
& & 23:33:56 +08:00
递归我能不用就不用。
& & 23:40:20 +08:00
@ 记得某本书里写过：我的程序员要是用递归去计算阶乘，我宁愿换人。
& & 23:49:43 +08:00
@ 代码大全。。。
& & 23:55:57 +08:00
递归的规则很简单
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)
再了解递归可以去看看点稍微复杂点的例子，像二分法求平方根，快速排序。
& & 00:01:21 +08:00
孩子买书去学吧，推荐 莫绍揆的《递归论》
& & 00:07:50 +08:00
@ 嗯，同样推荐SICP，很强调递归的说，尤其习题要做一下。
& & 00:15:12 +08:00
@ 同意，我也觉得递归是对一个问题的更容易的解决方式，同样也是更没运行效率的一种解决方式
& & 00:21:26 +08:00 via iPhone
递归可以写阶乘，不慢。
迭代就是加了一个计数参数的尾递归。
递归有些时候不用就搞不出来。
& & 00:22:20 +08:00 via iPhone
吐个血槽，scheme 读输入都是拿递归
& & 01:08:18 +08:00
写一点functional programming的东西 scala, haskell 不想递归也得递归
& & 01:30:22 +08:00
Programming With Nothing
& & 05:06:46 +08:00
可以学学分形几何嘛，娃哈哈哈哈，自相似
& & 05:11:29 +08:00
写 functional programming，把循环想成尾递归
& & 09:19:40 +08:00
我记得我之前学习Scala，因为其不支持break而苦恼，结果Google Groups上的人推荐我用递归代替循环……
& & 09:25:53 +08:00
说明你是一个比较勤快的人----&当你变懒了之后，你就会想用递归等等----当然，优秀的程序员都是“懒”的。
& & 09:57:53 +08:00
@ 什么是纯的程序员。。。
& & 10:09:39 +08:00 via iPad
@ 就是真正工作的时候很可能用不到。除非写很理论的东西
& & 10:13:37 +08:00
@ 赞同。递归简单理解就是函数调用函数，不过调用的函数是自己而已。
& & 10:22:34 +08:00
@ 也就是说你的意思是“纯的程序员”，就是搞理论的？
& & 10:30:24 +08:00
可以跟一遍这个课程：https://class.coursera.org/proglang-/class/index
虽然只是个大三大四的课，其中大部分 SML 和 Racket 写的作业都要用到递归，做完一遍就差不多养成习惯了。
& & 10:46:55 +08:00
这个我觉得主要靠练习，我刚开始接触递归的时候，也是像楼主一样搞不懂。 后来多想想，多练习，也发现没什么难的。
楼主可以从栈这方面理解，递归说白了就是不断的压栈呀，出栈...
& & 11:08:21 +08:00
用一段Haskell就习惯了，其实更多是一种思维训练，如果找出问题的规律，将其分解为更小规模的问题.
& & 11:10:26 +08:00
业余玩单片机的表示没法用递归，内存按字节数，一搞递归要吃多少内存啊
& & 11:14:36 +08:00
递归 很好么？？？ 小心栈溢出
& & 11:15:58 +08:00
一句话，学并且用 Clojure 。在类C的语言里，不要使用递归。
& & 11:23:57 +08:00
@ 经你一说觉得确实是这样，我再温习一遍数学归纳法
& & 11:26:14 +08:00
恩，以后递归的问题从这两点出发去考虑
& & 11:27:28 +08:00
@ 同忧心。
& & 11:30:59 +08:00
@ 当然单片机这种寸土寸金的地方就不考虑这些啦
& & 11:31:14 +08:00
@ 用尾递归
& & 11:39:14 +08:00
计算机上的递归实际上就是 栈+循环 而已。
& & 12:20:13 +08:00
& & 12:59:50 +08:00
@ 牛！太好了
& & 13:06:37 +08:00
@ 说递归有效率问题的，可以看下尾递归优化
& & 14:08:12 +08:00 via iPad
@ 是。我不和你说了，再说没钱了。刚注册
& & 15:42:17 +08:00
生产环境下谁用递归开除谁，无二话。
& & 18:10:02 +08:00
@ 谢谢，明天早上研究一下
& & 18:36:55 +08:00
去看 《The Little Schemer》 吧。
& & 18:52:42 +08:00
我觉得写递归要想清楚什么时候return。具体的问题你可以debug，不过切记测试数据要简单却不失代表性。不然不会单步到找不着北的。。。
& & 20:49:23 +08:00
学一门函数式语言。lisp,ML,haskell自动就会了
& & 00:25:42 +08:00 via Android
我不太习惯用迭代，这方面我该做什么加强。
& & 13:14:29 +08:00
@ 尾递归只能优化尾递归，又不能优化各种递归，如果是递归函数里调用两次递归(深搜二叉树)，这样还是没法优化啊。。， 所以递归递归效率的确不高
& & 13:54:27 +08:00
@ 但是树型递归这类问题，递归产生的cost是必须的，即使不用递归也需要手动维护栈或者类似的数据结构，和递归的耗费是一样的，这就不是递归本身的性能问题了，你没有其他的选择。
所以你说的效率不高其实是算法的问题，而不是递归的问题。
引入尾递归优化的价值在于，用更抽象的代码解决问题，并且没有额外的性能消耗。
& & 15:48:14 +08:00
@ 尾递归只是一个编译优化而已，没你说的那么神奇吧，还是那句话，尾递归只能优化在递归函数最后调用递归的问题，而且做法就是把这样的递归改成与for循环类似的样式；
递归的简洁、抽象是必须的，但是在实际系统里它的效率问题也很明显。你认为递归和手动维护这样的耗费是一样的，这个我觉的不准确，递归的性能消耗有这么几个方面：
1、它每次都需要把所有的局部变量压栈，不管这个局部变量还要不要用；
2、它是一个函数一个函数为单位进行调用的，调用函数是有消耗；
以上两个方面在迭代次数不大的时候其实不是啥问题，但是次数一多就会成为问题了；
而递归需要的消耗，在for循环一类的迭代里完全可以避免。
就拿深搜来说，一般用for循环迭代之前，都会先开一个容器(数组，字典都行)，把所有节点的初始状态保存进去，然后每遍历一个节点修改容器里相应的元素内容，很多在递归里需要的消耗（压栈，出栈，跳转等）在这就没有了；
尾递归优化当然是很好的东东，但是目前应该还没有可以把所有递归都优化的很好的法子；所以我感觉递归的效率还是有些低。
当然，递归最大的问题还是它很容易把栈给挤爆。。。
& & 16:25:22 +08:00
@ &一般用for循环迭代之前，都会先开一个容器(数组，字典都行)，把所有节点的初始状态保存进去，然后每遍历一个节点修改容器里相应的元素内容&
这做法整个一杯具啊. 比如考虑遍历一个N个节点的二叉树, 用DFS递归遍历的渐进空间复杂度只有O(logN), 开一个容器然后迭代的空间复杂度总是O(n). 如果要DFS的二叉树是平衡的那么递归的空间开销则可以直接忽略了. 遍历一颗1T节点的平衡二叉树所需要的堆栈桢也不会超过100个单位. 你有1T内存还拿不出100个函数调用的栈桢么?
递归的空间消耗是由递归的深度和tail call共同决定的. 在能保证递归深度的渐进增长率是可接受的情况下直接递归也不会有什么问题, 尤其是递归代码显然更简洁且易维护的情况下.
& & 16:33:18 +08:00
递归我能不用就不用+1
& & 16:37:23 +08:00
@ 发现野生帝老师
& & 20:14:18 +08:00
@ 大哥，我觉得你混淆了好多情况啊。。：
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(){
a();
}
b要存下；
while(!xxx){
int b
&(&(
}
b不用存；
因此，在理论上时间，空间一致的情况下，递归还有各种实现上的开销，所以效率低；
PS：这句话：“都会先开一个容器(数组，字典都行)，把所有节点的初始状态保存进去”，存的就是二叉树好吧，二叉树经常这么存储，然后在每个节点元素里加上个种信息。
本来还想在写点，但是看着已经写好多了，在写下去就太烦了。。，主要是觉得你没搞懂。。。还说我的法子不对。。有些不爽。。
& & 20:27:54 +08:00
递归除了让你感受到算法的奥妙的之外，基本毫无用处。况且，能不用递归，尽量不要用递归。不过这个思维过程比较有趣~
PS：我算是半吊子玩算法的。
& & 20:28:28 +08:00
@ 呃，一时手快，刚刚的回复打错了几个字
“1、时间复杂度” =& 想打的是“1、空间复杂度”
第5行“可以说是一个特例而已，也只能说是和空间相关。” =& 其实我想说的是，完全二叉树是性质很好一个种树。。
& & 20:36:10 +08:00 via iPhone
& & 20:45:51 +08:00
0. 呀, 如果度量算法空间复杂度还要算上数据本身占用的空间的话, 你能解释一下quicksort的O(logN)的空间复杂度是怎么得来的么?
1. 我前面提到的1T单位的空间是[存储]二叉树需要的空间, 而非执行递归调用所需的[栈空间];
2. 虽然某些方法能获得更好的渐进复杂度; 但这种[更好]有时只是&galactic improvments&. 你认为O(logN)和O(1)有多大的差距, 在你的计算机所能承受的数据范围内?
& & 21:05:15 +08:00
空间复杂度和渐进空间复杂度嘛，你本来说渐进空间复杂度，但是却说存储了节点后的算法（我原来给的算法）的渐进空间复杂度是O（N）。而这O（N）是dfs的空间复杂度。。。
1、至于一颗1T的树。。，具体的总有trick的法子可以不用一口读这么多的，但是递归同时要存储占用更多的栈空间；具体的我没啥数据，不过我以前多一个500多M的文件夹内txt文件（随机生成的）进行单词词频统计，用递归的法子把栈挤爆过；
2、 这个问题。。，和递归效率有关系吗，咱们没讨论这个吧。。
& & 21:14:57 +08:00
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);
& & 21:27:11 +08:00
即使所有的递归能弄成尾递归，调用函数的开销也会使速度变慢。当然，如果调用函数的开销只占所有开销很小一部分的话，还是用尾递归较好，用尾递归的代码更好看，更容易理解。
& & 21:33:40 +08:00
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
& & 21:37:16 +08:00
0. 晕... 抱歉我会错意了. 我本来想说因为遍历的是tree所以可以不维护visited set的 = =
1. 前面说好的要[把所有节点的初始状态保存进去]呢, 难道这一步不需要O(|V|)的空间么
& & 21:52:57 +08:00
@ 好吧我知道了, 乃刚才的讨论都是针对任意图的DFS, 我只想到遍历树了
& & 22:04:55 +08:00
能用循环尽量用循环
递归是个坑
不好调试也容易崩溃，尤其深度过大的时候容易爆栈
图灵证明过
循环和递归是等价的
DFS可以无缝转换成BFS
& & 22:11:52 +08:00
@ 奥，这样啊。。，好像是哦。。,= =
& & 22:41:26 +08:00
@ 尾递归的优化就是把函数调用优化成循环。。。
& & 10:37:12 +08:00
@ 不是吧！？，尾递归的优化是去除爆栈的可能性，还是会产生函数调用的消耗的。
& · & 623 人在线 & 最高记录 3541 & · &
创意工作者们的社区
World is powered by solitude
VERSION: 3.9.8.1 · 21ms · UTC 21:44 · PVG 05:44 · LAX 14:44 · JFK 17:44? Do have faith in what you're doing.没有更多推荐了，
不良信息举报
举报内容：
关于递归的性能问题
举报原因：
原文地址：
原因补充：
最多只允许输入30个字
加入CSDN，享受更精准的内容推荐，与500万程序员共同成长！递归（recursion）就是子程序（或函数）直接调用自己或通过一系列调用语句间接调用自己，是一种描述问题和解决问题的基本方法。
&&& 递归通常用来解决结构自相似的问题。所谓结构自相似，是指构成原问题的子问题与原问题在结构上相似，可以用类似的方法解决。具体地，整个问题的解决，可以分为两部分：第一部分是一些特殊情况，有直接的解法；第二部分与原问题相似，但比原问题的规模小。实际上，递归是把一个不能或不好解决的大问题转化为一个或几个小问题，再把这些小问题进一步分解成更小的问题，直至每个小问题都可以直接解决。因此，递归有两个基本要素：
&&& （1）边界条件：确定递归到何时终止，也称为递归出口。
&&& （2）递归模式：大问题是如何分解为小问题的，也称为递归体。递归函数只有具备了这两个要素，才能在有限次计算后得出结果
在递归函数中，调用函数和被调用函数是同一个函数，需要注意的是递归函数的调用层次，如果把调用递归函数的主函数称为第0层，进入函数后，首次递归调用自身称为第1层调用；从第i层递归调用自身称为第i+1层。反之，退出第i+1层调用应该返回第i层。
递归函数的内部执行过程
&&& 一个递归函数的调用过程类似于多个函数的嵌套的调用，只不过调用函数和被调用函数是同一个函数。为了保证递归函数的正确执行，系统需设立一个工作栈。具体地说，递归调用的内部执行过程如下：
&&& （1）运动开始时，首先为递归调用建立一个工作栈，其结构包括值参、局部变量和返回地址；
&&& （2）每次执行递归调用之前，把递归函数的值参和局部变量的当前值以及调用后的返回地址压栈；
&&& （3）每次递归调用结束后，将栈顶元素出栈，使相应的值参和局部变量恢复为调用前的值，然后转向返回地址指定的位置继续执行。
以阶乘为例说明递归的工作原理：
long ff(int n) { if(n&0)
printf("n&0,input error"); else if(n==0||n==1)
f=1; //为什么f=1,就不再继续递归调用？
f=ff(n-1)*n;//这一步到底是怎么工作的？ return(f); }
首先要清楚，就是某个函数直接或间接地调用了自身，这种调用方式叫做。说白了，还是函数调用。既然是函数调用，那么就有一个雷打不动的原则：所有被调用的函数都将创建一个副本，各自为调用者服务，而不受其他函数的影响。
你的ff函数，递归多少次，就有多少个副本，再利用内存的栈式管理，反向退出。这个最好找一下&栈&这方面的东西看看，挺容易的，就像子弹匣一样，先进后出。
你不理解，很有可能是因为误以为该这几行代码被反复使用了。，这是不对的，因为就像刚才说的，一旦被调用，他将在内存中复制出一份代码，再被调用就再复制一份，换句话说，你可以吧同一个函数的多次调用理解称谓多个不同函数的一次调用，这样也会会简单些。
再说=1和=0是为什么退出。递归，很需要注意的就是死递归，也就是说，某一个函数进入了无限调用自身的情况，永无止境地消耗内存等资源，这在编程方面是一大忌。但凡是递归的函数，一定会在某一个地方存在能够返回上一层函数的代码，否则必定死递归。ff函数中，那个else就是返回的出口，你可以这样想，如果没有那个if来进行判断，你递归到什么时候算完？ff是不是会一直调用自己呢？别指望被调用的函数会自动结束，因为一旦某个函数A中调用了函数B（或者自己），那么A中的代码会停在调用的位置，而转向B中去执行，同理，如果B又调用函数C，那么B又停在调用的位置，去执行C，如果无限调用，那么程序是永远不会结束的。当然，也有这种情况，A调用B，然后继续自己的代码，不管B的死活，这种不在我们的讨论范围内，因为那牵扯到另一种编程方式：。（我们现在说的是）
给你拆极不看看吧：
一层执行到f=ff(3-1)*3;停止，执行二层ff(3-1),也就是ff(2)
二层执行到f=ff(2-1)*2;停止，执行三层ff(2-1)，也就是f(1)
三层执行到else if(n==0||n==1) f=1;然后return(f)到二层的ff(2-1)的位置，二层继续执行
二层执行f=1*2; 然后就return(f)到一层ff(3-1)的位置，一层继续执行
一层执行f=2*3; 然后就return(f)到了最初调用ff(3)的main函数里，所以就得到y=6
大体过程就是这样的
这里每次一层都相当于一个不同的函数，你可以给他们为ff1,ff2,ff3.....这样就不混了。只要注意一点，调用一次，不是在代码本身上执行，而是会复制出一份在执行，虽然不太恰当，但足以说明问题。
阅读(...) 评论()没有更多推荐了，
不良信息举报
举报内容：
递归与循环相比时间优势的真正来源
举报原因：
原文地址：
原因补充：
最多只允许输入30个字
加入CSDN，享受更精准的内容推荐，与500万程序员共同成长！