这是一个创建于 3453 天前的主题，其中的信息可能已经有所发展或是发生改变。
网上看到讨论镜像二叉树的问题多有不用递归的前提条件，如果用递归这个问题就简单多了。那么不用递归，基本也都用到了栈，那么问题是，用栈有什么实际上的好处吗？感觉用栈并不会节省空间，那么不用递归的要求仅仅是为了提高问题难度吗？在实际生产中，大家是如何处理镜像二叉树的？大家的考虑是怎样的？
6 条回复 • 2015-06-13 10:59:56 +08:00
 |
1
sumhat 2015-06-12 20:34:19 +08:00  2
系统栈和用户栈的差别。递归的主要问题是会栈溢出，自己开的空间则不受这个限制。
|
 |
2
wy315700 2015-06-12 20:34:24 +08:00 1
日常编程中，一般会要求不使用递归，尤其是Python等语言，递归的性能简直低下。
|
 |
3
weyou 2015-06-12 21:00:16 +08:00 1
除了@sumhat所讲的栈溢出的问题之外，使用用户栈会使性能提升，函数调用栈除了所操作的数据之外，还有函数参数的传递，返回值的拷贝等额外的开销。
|
 |
4
ffffwh 2015-06-12 22:53:41 +08:00 1
万能法(前方装逼)：递归->CPS->trampolining
https://gist.github.com/unknownzerx/dffb4346fe2f7429423b 性能？who cares... |
 |
5
billlee 2015-06-12 23:02:31 +08:00 1
递归的性能差，可能发生运行栈溢出。
另外补充一点，遍历二叉树不一定用栈，深度优先遍历用栈，广度优先遍历用队列。 |
 |
6
hooluupog 2015-06-13 10:59:56 +08:00 1
首先，不用递归并非完全是指用栈去模拟递归。栈模拟递归和非递归算法(比如迭代)是两个概念。
很多情况下递归符合人的思维方式，但性能偏弱，而且有时候递归深度有限制，在没有尾递归优化的编译器上尤为如此。 非递归的算法往往更难理解，但会获得较好的性能。 比如汉诺塔问题，既可以用递归实现，又可以用栈去模拟递归，同时还有比较难以理解的非递归算法。 同样Fibonacci问题也有非递归的解法，而实际环境中，命令式语言基本上都是去用非递归的方法去解Fibonacci类似的问题。很多人喜欢用Fibonacci递归算法去测试一个编程语言的性能，实际上这个是最坏的一种测试情形，和实际完全脱节。 |
Select Language