algorithm - 什么是递归树？

Question

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

Answer 1

递归树可以展示递归在解决您的问题时可能有多么有用，并且还可以帮助揭示更坏/最好的情况。例如，如果您的二分搜索算法的递归树总是采用最正确的路径，那么您可能处于更糟糕的情况（因为您的程序没有分支，为什么还要使用树来表示它？）。在一组输入上绘制算法的递归操作树也可以在您的脑海中激发关于如何将递归程序更改为迭代的想法，这可能会或可能不会节省大量内存/时间。

或者，它可以使您的递归程序看起来非常好，因为您可能会发现它在进入下一层之前填充了几乎所有的叶子，并让您在树上快速操作。一个很好的例子是红黑二叉搜索树，但是用递归的方式比合并排序更难映射。