递归树
概述
递归树 是一种将递归关系式可视化为树形结构的分析方法。每个节点表示一次递归调用的代价，通过逐层展开和求和，直观地推导出递归式的解，也是理解主定理的直观基础。
定义
递归树
递归树是一棵有根树，其中：
- 每个节点表示一次递归调用产生的代价。
- 根节点的代价为递归式的非递归项 。
- 每个内部节点有 个子节点（对应 个子问题），子节点的代价为 。
- 叶节点的代价为 （基础情形）。
- 总代价为树中所有节点代价之和。
核心性质
- 递归树将递归式的展开过程可视化，便于直观理解各层代价的分布。
- 树的深度为 （递归终止层数），每层有 个节点。
- 逐层求和后，总代价通常呈现为几何级数，可直接求和得到渐近界。
- 递归树法特别适合生成”好猜测”，再用代入法严格证明。
- 递归树也是主定理三种情况分类的直观解释：叶节点代价 vs. 根节点代价的对比。
章节扩展
第4章：分治策略
- 4.4 递归树法：系统性地介绍递归树的构造和求和方法，以 等为例进行详细推导。
- 4.5 主定理：递归树的三种代价分布模式对应主定理的三种情况。
- 4.6 连续主定理的证明：使用递归树方法证明连续主定理。