递归树是什么？

Question

递归树是什么？

algorithmsortingrecursion

5

在阅读更多关于归并排序的内容时，我遇到了递归树。什么是递归树？它们有助于解决递归问题吗？通过绘制递归树我们能实现什么？谷歌没有帮到我。

- Ganesh Hoolageri

2

这可能是一个更适合程序员SE的问题。 - thegrinner

1

你确定谷歌帮不了忙吗？我刚刚找到了这个：http://en.wikipedia.org/wiki/Recursive_tree - Geeky Guy

谷歌很快就把我带到了这里(http://www.cs.cornell.edu/courses/cs3110/2012sp/lectures/lec20-master/lec20.html)。那似乎基本上已经讲得很清楚了。 - Bernhard Barker

@Renan：递归树！= 递归树 - Don Roby

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Rob G · Accepted Answer

递归树可以展示递归在解决问题时有多么有用，同时也可以帮助揭示最好/最坏情况。例如，如果二分查找算法的递归树总是沿着最右侧的路径进行，那么您可能处于最坏情况（因为程序没有分支，为什么要使用树来表示它？）。绘制算法在一组输入上的递归操作的树状图也可以激发您的思路，使您想到如何将递归程序更改为迭代程序，这可能会节省大量内存/时间。

另一方面，它也可能使您的递归程序看起来非常出色，因为您可能会发现它填满了几乎所有的叶子，然后才进入下一层，并为您快速地操作树奠定基础。红黑二叉搜索树就是一个很好的例子，但是它比归并排序更难以以递归方式映射出来。