什么是递归树？

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

2013-08-01 Ganesh Hoolageri

这对于Programmers SE来说可能是一个更好的问题。 – thegrinner

你确定Google不会帮忙吗？我刚刚发现这个：http://en.wikipedia.org/wiki/Recursive_tree – Renan

谷歌很快带领我[在这里]（http://www.cs.cornell.edu/courses/cs3110/2012sp/lectures/lec20-主/ lec20.html）。这似乎涵盖了它。 – Dukeling

递归树可以证明递归在解决问题中有多大用处，还可以帮助揭示更坏/最好的情况。例如，如果你的二分查找算法的递归树总是选择最正确的路径，那么你可能会遇到更坏的情况（因为你的程序不是分支的，为什么还要用树来表示它？）。通过一组输入绘制算法的递归操作树，也可以激发您思考如何将递归程序更改为迭代，这可能会或可能不会节省大量内存/时间。

或者它可以使你的递归程序看起来非常好，因为你可能会发现它填满了所有的叶子，然后再移动到下一层，并设置你在树上快速操作。一个很好的例子就是红黑二叉搜索树，但以递归方式绘制出来要比合并排序困难得多。

来源

2013-08-01 12:15:54

什么是递归树？

回答

相关问题