有关镜像二叉树的疑问

[sneezry]

网上看到讨论镜像二叉树的问题多有不用递归的前提条件，如果用递归这个问题就简单多了。那么不用递归，基本也都用到了栈，那么问题是，用栈有什么实际上的好处吗？感觉用栈并不会节省空间，那么不用递归的要求仅仅是为了提高问题难度吗？在实际生产中，大家是如何处理镜像二叉树的？大家的考虑是怎样的？

[sumhat]

系统栈和用户栈的差别。递归的主要问题是会栈溢出，自己开的空间则不受这个限制。

[wy315700]

日常编程中，一般会要求不使用递归，尤其是Python等语言，递归的性能简直低下。

[weyou]

除了@sumhat所讲的栈溢出的问题之外，使用用户栈会使性能提升，函数调用栈除了所操作的数据之外，还有函数参数的传递，返回值的拷贝等额外的开销。

[ffffwh]

万能法(前方装逼)：递归->CPS->trampolining
https://gist.github.com/unknownzerx/dffb4346fe2f7429423b

性能？who cares...

[billlee]

递归的性能差，可能发生运行栈溢出。
另外补充一点，遍历二叉树不一定用栈，深度优先遍历用栈，广度优先遍历用队列。

[hooluupog]

首先，不用递归并非完全是指用栈去模拟递归。栈模拟递归和非递归算法(比如迭代)是两个概念。

很多情况下递归符合人的思维方式，但性能偏弱，而且有时候递归深度有限制，在没有尾递归优化的编译器上尤为如此。
非递归的算法往往更难理解，但会获得较好的性能。
比如汉诺塔问题，既可以用递归实现，又可以用栈去模拟递归，同时还有比较难以理解的非递归算法。
同样Fibonacci问题也有非递归的解法，而实际环境中，命令式语言基本上都是去用非递归的方法去解Fibonacci类似的问题。很多人喜欢用Fibonacci递归算法去测试一个编程语言的性能，实际上这个是最坏的一种测试情形，和实际完全脱节。