递归树

概述

递归树（Recursion Tree）是一种分析递推关系的可视化工具。它将递推关系展开为一棵树结构，其中每个节点表示一次递归调用的代价，每层表示同一递归深度上所有调用的代价之和。通过逐层求和并累加，可以得到递推关系的渐近解。递归树是理解主定理三种情形的直观方法。

定义

递归树（Recursion Tree）

对于递推关系 $T(n)=aT(n/b)+f(n)$，递归树的构造规则如下：

1. 根节点：代价为 $f(n)$，表示合并步骤的代价
2. 子节点：根节点有 $a$ 个子节点，每个子节点的代价为 $f(n/b)$，代表 $a$ 个规模为 $n/b$ 的子问题的合并代价
3. 递归展开：每个子节点再展开为 $a$ 个孙节点，代价为 $f(n/b^2)$，以此类推
4. 叶节点：当问题规模缩小到基本情况（通常为常数）时停止展开

递归树的总代价为所有层代价之和：

$T(n)={\sum }_{i=0}^{{\log }_{b}n}{a}^i\cdot f(n/b^i)$

核心性质

性质	描述	备注
层数	树的深度为 ${\log }_{b}n$（假设基本情况在规模为 1 时）	对应递归的深度
每层节点数	第 $i$ 层有 $a^i$ 个节点	指数增长
叶节点数	共 $a^{{\log }_{b}n}=n^{{\log }_{b}a}$ 个叶节点	即基本情况的总数
层代价	第 $i$ 层代价为 $a^i\cdot f(n/b^i)$	决定总代价的增长模式
总代价	各层代价之和	通过求和得到渐近解

递归树与主定理的对应

递归树直观地解释了主定理的三种情形：

• 情形一（叶节点主导）：层代价随深度递减，叶节点层代价最大。总代价 $\Theta (n^{{\log }_{b}a})$
• 情形二（各层相当）：每层代价相同（或仅差 $\log$ 因子）。总代价 $\Theta (n^{{\log }_{b}a}\log n)$
• 情形三（根节点主导）：层代价随深度递增，根节点代价最大。总代价 $\Theta (f(n))$

应用场景

• 直观理解主定理：递归树是主定理的几何直觉来源
• 分析不满足主定理条件的递推：如 $T(n)=T(n/3)+T(2n/3)+n$（子问题规模不等）
• 推导主定理：通过递归树的层代价求和严格证明主定理
• 教学工具：帮助初学者理解递推关系的求解过程

示例：归并排序的递归树

对于 $T(n)=2T(n/2)+\Theta (n)$：

层 $i$	节点数	每节点代价	层代价
0	1	$cn$	$cn$
1	2	$cn/2$	$cn$
2	4	$cn/4$	$cn$
…	…	…	…
$\log n$	$n$	$c$	$cn$

共 $\log n+1$ 层，每层代价 $cn$，总代价 $\Theta (n\log n)$。

参见

• 主定理 — 递归树分析的形式化结论
• 递归关系式 — 递归树分析的对象
• 分治法 — 产生递推关系的算法策略
• 归并排序 — 递归树分析的典型示例