理解递归树：斐波那契、调用次数与记忆化
一棵树记录全部调用，一条路径决定峰值深度。用斐波那契的九节点图和实际计数，看清重复子问题，再比较缓存与循环。
用递归树看完整的工作量
本篇覆盖知识点 32—37。沿用《Hello 算法》的编号约定：第 1 项为 0，第 2 项为 1。先看朴素递归，再以计数说明重复子问题，最后引入记忆化与循环实现。
知识点 32：先确定编号和基本情况
本篇定义 F(1)=0、F(2)=1，且 n≥3 时 F(n)=F(n−1)+F(n−2)。因此 F(3)=1、F(4)=2、F(5)=3、F(6)=5。另一种常见写法从 F(0)=0 开始；两者的参数编号相差 1，比较输出前必须统一约定。
基本情况给出确定的答案；递推关系说明如何组合两个子问题。下面代码约定 n 为正整数。没有输入校验的教学版本不应直接用于任意输入：n=0 或负数将不能到达 1、2 这两个基本情况。
def fib(n):
if type(n) is not int or n < 1:
raise ValueError("n must be a positive integer")
if n <= 2:
return n - 1
return fib(n - 1) + fib(n - 2)
print([fib(n) for n in range(1, 9)])知识点 33、35：一个节点对应一次调用
递归树记录所有调用之间的父子关系。根节点是起始调用，子节点是它发起的下一层调用。相同函数、相同参数再次出现，也要画成另一个节点，因为它确实重新执行了一次。
fib(5) 的结果是 3，但得到这个答案需要进入 9 次 fib。两个 fib(3) 都分别计算 fib(2)+fib(1)，不会因为名称相同就自动共享此前结果。这正是重复子问题。
递归树包含整个运行过程的记录。它不是某个瞬间的调用栈快照；不能把九个节点全都理解为同时保留的九个帧。
知识点 34：两个分支默认按顺序执行
Python 按从左到右的顺序求值这个加法表达式：先完整求出 fib(n−1)，保留左侧结果，再求 fib(n−2)，最后相加。下面的 fib(3) 先进入 2、返回，再进入 1、返回。递归树左右并列的画法没有创造并行任务。
这也说明，“递完所有节点再统一归”不是多分支递归的真实时间顺序：左分支会先深入并返回，接着才进入右分支。在普通单线程调用中，上层在等待当前子调用。
def traced_fib(n):
print("enter", n)
if n <= 2:
result = n - 1
else:
left = traced_fib(n - 1)
right = traced_fib(n - 2)
result = left + right
print("leave", n, result)
return result
print("answer", traced_fib(3))知识点 36：调用总数指数增长，峰值深度线性增长
设 C(n) 为朴素 fib 的调用总数，有 C(1)=C(2)=1，C(n)=1+C(n−1)+C(n−2)。加上当前调用本身，才得到完整总数。该递推的增长为 Θ(φⁿ)，其中 φ≈1.618；常见的 O(2ⁿ) 是较宽松的上界。
最长调用链则沿 n、n−1、…、2 推进。按根为第 1 层的约定，n≥2 时最大 fib 深度为 n−1；渐近增长为 Θ(n)。所以指数调用总数与线性栈空间并不矛盾：左右分支按顺序执行，只保留当前路径与待完成的上层状态。
下例把 value、calls、peak 分别打印出来。n=6 得到 5、15、5；n=10 得到 34、109、9。峰值只统计内部 solve，包装函数没有算进去。
def measure_fib(n):
calls = 0
peak = 0
def solve(k, depth):
nonlocal calls, peak
calls += 1
peak = max(peak, depth)
if k <= 2:
return k - 1
return solve(k - 1, depth + 1) + solve(k - 2, depth + 1)
value = solve(n, 1)
return value, calls, peak
for n in (6, 10):
print(n, *measure_fib(n))知识点 37：记忆化避免相同输入的重复计算
把参数与已算出的结果保存在缓存中。再次遇到相同参数时，直接返回缓存结果，跳过函数体的重复求解。Python 3.9 起可以用 functools.cache；它相当于不限制容量的函数结果缓存。
下例仅处理正整数。在这个单线程示例中，首次 fib_memo(6) 实际求解 n=1…6 共 6 个不同输入；之后遇到的三个重复请求命中缓存。再次调用 fib_memo(6) 时，直接命中已有结果。缓存命中也有查找成本，所以不能把“函数体未执行”描述为整个调用完全没有工作。
冷缓存首次计算按常数算术与常见哈希查找模型，需要 O(n) 次求解、O(n) 个缓存条目，以及仍为 O(n) 的调用深度。记忆化减少重复工作，不把深递归自动改成浅递归。
from functools import cache
@cache
def fib_memo(n):
if type(n) is not int or n < 1:
raise ValueError("n must be a positive integer")
if n <= 2:
return n - 1
return fib_memo(n - 1) + fib_memo(n - 2)
print(fib_memo(6))
info = fib_memo.cache_info()
print(info.hits, info.misses, info.currsize)
print(fib_memo(6))
print(fib_memo.cache_info().hits)缓存的适用条件：答案必须与键对应
缓存参数需要可哈希，并且应当足以确定答案。只按 n 缓存这份数学函数是合理的；如果答案依赖外部文件、时间、配置或数据库版本，缓存键和失效规则就必须包含这些变化，否则可能返回旧结果。
无限容量缓存会长期保留参数与返回值的引用。需要控制内存时，可考虑有界 lru_cache 或主动清理；容量不足导致条目淘汰时，就不再保证所有子问题都只求解一次。带有必须每次执行的日志或写操作的函数，也不能不加分析地缓存。
官方文档还指出，线程安全的缓存结构不意味着并发冷请求绝对只执行一次函数体。这里“一次求解一个输入”的计数只针对本篇的单线程、有足够缓存且初始为空的示例。
进一步比较：从基本情况向前推进
斐波那契只依赖前两项，可以从 0、1 开始逐项推进，保存两个变量。a, b = b, a + b 的右侧先用更新前的 a、b 求值，再绑定新值。第 n−1 次推进后，a 对应本篇的 F(n)。
在通常的算术成本模型下，这个循环执行 O(n) 次加法，保留固定数量的整数变量，不需要递归栈和 n 个缓存条目。Python 大整数的位数会随结果增长，所以固定数量的变量不等于恒定字节，也不能在位成本模型下把每次加法一概当作 O(1)。
递归是组织调用的方式；分治是拆分问题的策略。斐波那契的子问题有重叠，适合用记忆化减少重复计算，不能因此把所有递归都称为分治。
def fib_loop(n):
if type(n) is not int or n < 1:
raise ValueError("n must be a positive integer")
a, b = 0, 1
for _ in range(n - 1):
a, b = b, a + b
return a
print([fib_loop(n) for n in range(1, 9)])复盘：把树、路径与缓存分开画
- 手画 fib(5) 的九个调用节点，再单独画进入最深处时的调用栈。
- 为什么两个 fib(3) 在树上是两个节点？它们返回什么相同值？
- 给 fib(6) 加缓存后，减少的是什么，保留的是什么？
- 把缓存改成容量为 2，还能直接沿用“每个输入只求解一次”的说明吗？
展开参考答案
整棵树记录累计调用，栈只记录当前未完成路径；两个 fib(3) 都返回 1，但朴素版本会重复求解；缓存减少重复求解，仍保留递归调用链及缓存数据；容量不足可能导致重新计算，必须检查实际淘汰行为。
本文调用数量与深度由代码计数及递推关系推导，未将这些计数当作运行时间基准。
本系列的来源与许可
本篇是《Hello 算法》相关主题的重新组织与补充讲解。署名、修改说明及 CC BY-NC-SA 4.0 许可见 系列来源说明；对应知识点和官方依据均可从索引核验。