如何根据递归关系确定递归树的高度？

Question

如何确定在处理递归运行时构建的递归树的高度？它与确定常规树的高度有何不同？

alt text http://homepages.ius.edu/rwisman/C455/html/notes/Chapter4/ch4-9.gif

编辑:对不起,我的意思是添加如何从递归关系中获取递归树的高度.

Answer 1

如果递归是T(n)= aT(n/b)+ f(n)的形式,那么树的深度是n的对数基数b.

例如,2T(n/2)+ n重现将具有深度为lg(n)的树(n的对数基数2).

Answer 2

递归树的高度取决于所讨论的递归算法。并非所有分治算法都具有统一高度的树，就像并非所有树结构都具有统一高度一样。如果无法确定算法的最大可能高度，或者需要在运行时计算树的实际高度，则可以使用递归函数的全局变量，在进入函数时递增它，并递减它在函数退出时。该变量将指示递归过程的当前级别。如有必要，您可以在第二个变量中维护该变量的最大值。