为什么直接使用递归计算斐波那契数列效率极低？

适用条件

• 算法使用没有记忆化的朴素递归。
• 递推关系为 $f(n) = f(n-1) + f(n-2)$。

理解与推导

1. 为目标计算（如 $f(7)$）构建递归树。
2. 向下追踪分支以观察生成的子问题。
3. 识别出相同的子问题（例如 $f(4)$）在不同分支中多次出现。
4. 得出结论：算法冗余地重新计算这些重叠的子问题，导致指数级时间复杂度。

例子

随着树向下生长，可以清楚地看到 $f(4)$、$f(3)$ 和 $f(2)$ 等节点在不同分支中被反复生成。这个视觉过程深刻地揭示了朴素递归算法中固有的大量冗余计算。

容易误解的地方

• 初学者可能认为递归只是调用自身，而没有意识到二叉分支递归会产生指数级数量的重复子问题。
• 假设递归树只包含唯一的节点，没有任何重叠的子问题。

观看对应讲解

继续追问

• 如何使用递归树分析递归算法的时间复杂度？
• 这个递归算法的时间复杂度是多少？
• 视频如何区分树的实际绘制和理论估算？