视频如何构建递归树来分析 $f(7)$ 的递归计算过程？

适用条件

• 递推关系为 $f(n) = f(n-1) + f(n-2)$。
• 基本情况为 $f(1) = 1$ 和 $f(2) = 1$。
• 目标计算为 $f(7)$。

理解与推导

1. 将目标计算 $f(7)$ 设为树的根节点。
2. 应用递归公式将 $f(7)$ 拆分为两个子节点：$f(6)$ 和 $f(5)$。
3. 继续将每个非基本情况节点拆分为两个子节点（例如，$f(6)$ 拆分为 $f(5)$ 和 $f(4)$）。
4. 重复此过程，直到所有叶子节点到达基本情况 $f(1)$ 或 $f(2)$。
5. 观察生成的倒置二叉树，以查看完整的递归调用序列。

例子

讲师绘制了一个以 $f(7)$ 为根节点的递归树，向下分支到 $f(6)$ 和 $f(5)$，然后将 $f(6)$ 进一步分解为 $f(5)$ 和 $f(4)$，依此类推，形成一个倒置的二叉树。

容易误解的地方

• 认为递归树只代表自顶向下的问题分解，而忽略了自底向上的结果聚合。
• 假设树在固定深度停止扩展，而不是在到达基本情况 $f(1)$ 或 $f(2)$ 时停止。

观看对应讲解

继续追问

• 为什么直接使用递归计算斐波那契数列效率极低？
• 如何使用递归树分析递归算法的时间复杂度？
• 递归树中每层的节点数遵循什么规律？