形式陈述

递归树法把递推式如 $T(n)=aT(n/b)+f(n)$ 展开为一棵调用树：第 $i$ 层有 $a^i$ 个规模 $n/b^i$ 的子问题，层成本为 $a^{i}f(n/b^i)$，深度约 ${\log }_{b}n$，总成本为各层成本与叶成本之和。该方法是推导和猜测渐近界的工具；最后仍需处理取整、基例并用代入法或主定理严格证明。

直觉

递推式把工作分散在不同层。观察每层工作是递增、递减还是同阶，往往一眼可看出总成本由根、所有层还是叶子主导。

例子与边界

归并排序 $T(n)=2T(n/2)+\mathrm{\Theta }(n)$ 每层成本 $\mathrm{\Theta }(n)$，有 $\mathrm{\Theta }(\log n)$ 层，总计 $\mathrm{\Theta }(n\log n)$。$T(n)=T(n/2)+n$ 的层成本构成几何级数，总计 $\mathrm{\Theta }(n)$。递归树中节点数不能只乘“层数”，因为每层子问题大小变化。非均匀递推如 $T(n)=T(n/3)+T(2n/3)+n$ 也可画树，但深度不齐，需按路径或总规模仔细求和。

推论与应用

递归树法用于分治算法复杂度设计、主定理直觉和非标准递推估计，能揭示算法在哪一层消耗主要资源。

参考资料

• Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein, Introduction to Algorithms, 4th ed., MIT Press, 2022，Parts I–VI。
• Jon Kleinberg and Éva Tardos, Algorithm Design, Pearson, 2005，Chs. 1–13。