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

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

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

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

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

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

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

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

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

递归我能不用就不用+1

@unionx 发现野生帝老师

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

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

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

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

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

反复练习

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

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

@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

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

@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

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

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

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

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

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

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