请大家指教一下：分别使用递归和栈遍历树，性能会差多少？
请大家指教一下：分别使用递归和栈遍历树，性能会差多少？

------解决方案--------------------
应该是栈的性能高一点吧
------解决方案--------------------
使用递归和栈遍历树,到底是那个方法效率好，这要看具体情况，
楼上的说栈的性能好，但是有时树的分支很多时，光压栈，出栈操作就有好多
------解决方案--------------------
没太大区别
------解决方案--------------------
不一定,看情况;
有的需要没试,一般情况递归效率低;
------解决方案--------------------

引用楼主 ipec 的帖子:

请大家指教一下：分别使用递归和栈遍历树，性能会差多少？

------解决方案--------------------
使用递归的性能基本上比自己使用栈快一些, 但是递归很可能会中途用光栈而使用程序退出, 但自己实现的堆栈一般很难这样, 因为以前比较过这两种方式, 在数据量不是非常大时, 递归取得胜利, 别人说, 很可能是编译器对递归进行了优化.
------解决方案--------------------
说说我的看法。

递归是进行的栈（数据结构）操作，并且是在栈（内存）上进行的，所以压栈出栈是很快的（指针偏移）；
而用迭代取代递归就会使用栈（数据结构）。

要比较性能的话，就要看迭代时使用的栈是怎样实现的，如果单纯的用int[] stack这样来模拟LIFO行为，其实和递归没太大区别，以为基本类型也是直接在栈（内存）上进行；要是用new Stack(),比如类库中的Stack来实现，那么显然直接使用递归效率更高。

…………………………………………………………………………………………………………
上面说的这些都是假设在一样的设计前提下。

然而设计的优劣对效率的影响比前面说的系统层面上的效率要大的多，所以“云上飞翔”的阿克曼展示的效率问题其实不在于递归和使用栈（数据结构）的不同，而在于设计上。

阿克曼函数如果直接用递归实现，那么它的算法复杂度是以2^n级别增长的。如果画一棵递归树就会发现，递归时，有很多分支具有完全一样的调用。

而使用迭代来计算阿克曼函数，就可以避免这个庞大的递归树。
但是也可以用递归+备忘录(一种设计方法，第一次递归，再次调用直接读取)来达到和迭代一样的进出栈次数。

…………………………………………………………………………………………………………
还有一点，编译器会对递归做出优化，比如尾部递归会被优化为使用迭代。这是编译器行为。
递归有个致命的缺点所以不建议使用，由于使用的是栈内存，如果压栈很深，一次一次的进栈最终会消耗完栈内存。

…………………………………………………………………………………………………………
一家之言，有不对的地方多包涵。