如何手动统计带记忆化的Python递归函数fb的调用次数？

需要统计以下带记忆化的Python递归函数fb的调用次数：

def fb(n, d):
    if n in d:
        return d[n]
    else:
        ans = fb(n-1, d) + fb(n-2, d)
        d[n] = ans
        return ans
d = {1:1, 2:2}
print(fb(8, d))
print(d)

理解该函数基本逻辑，但无法手动统计递归调用次数。通过代码或查看字典d可知最终递归调用次数为13，但不理解为何是这个结果。原本认为每个非缓存的n会触发两次递归调用，直到n为1或2，但实际运行打印n的代码：

def fb(n, d):
    if n in d:
        return d[n]
    else:
        print(n)
        ans = fb(n-1, d) + fb(n-2, d)
        d[n] = ans
        return ans
d = {1:1, 2:2}
print(fb(8, d))

输出为：

8
7
6
5
4
3
34

想了解该函数的内部执行逻辑，以及手动统计递归调用次数的思路。

一、函数内部执行逻辑拆解 #

从fb(8, d)开始一步步跟踪执行过程（初始缓存d={1:1,2:2}）：

1. 调用fb(8)：8不在缓存中，打印8，先调用fb(7)
2. 调用fb(7)：7不在缓存中，打印7，先调用fb(6)
3. 调用fb(6)：6不在缓存中，打印6，先调用fb(5)
4. 调用fb(5)：5不在缓存中，打印5，先调用fb(4)
5. 调用fb(4)：4不在缓存中，打印4，先调用fb(3)
6. 调用fb(3)：3不在缓存中，打印3，先调用fb(2)
7. 调用fb(2)：2在缓存中，直接返回2，第1次缓存命中调用
8. 回到fb(3)，调用fb(1)
9. 调用fb(1)：1在缓存中，直接返回1，第2次缓存命中调用
10. fb(3)计算得2+1=3，存入缓存d[3]=3，返回3，第1次非缓存调用完成
11. 回到fb(4)，调用fb(2)
12. 调用fb(2)：2在缓存中，直接返回2，第3次缓存命中调用
13. fb(4)计算得3+2=5，存入缓存d[4]=5，返回5，第2次非缓存调用完成
14. 回到fb(5)，调用fb(3)
15. 调用fb(3)：3已在缓存中，直接返回3，第4次缓存命中调用
16. fb(5)计算得5+3=8，存入缓存d[5]=8，返回8，第3次非缓存调用完成
17. 回到fb(6)，调用fb(4)
18. 调用fb(4)：4已在缓存中，直接返回5，第5次缓存命中调用
19. fb(6)计算得8+5=13，存入缓存d[6]=13，返回13，第4次非缓存调用完成
20. 回到fb(7)，调用fb(5)
21. 调用fb(5)：5已在缓存中，直接返回8，第6次缓存命中调用
22. fb(7)计算得13+8=21，存入缓存d[7]=21，返回21，第5次非缓存调用完成
23. 回到fb(8)，调用fb(6)
24. 调用fb(6)：6已在缓存中，直接返回13，第7次缓存命中调用
25. fb(8)计算得21+13=34，存入缓存d[8]=34，返回34，第6次非缓存调用完成

统计总调用次数：非缓存调用（进入else分支）共6次，缓存命中调用共7次，6+7=13次，与结果一致。

二、手动统计递归调用次数的思路 #

1. 区分两种调用类型 #

• 缓存命中调用：直接返回缓存值，不会触发新递归，次数等于初始缓存键的被调用次数，加上后续存入缓存的键的被调用次数。
• 非缓存调用：每个未缓存的n会触发两次递归，但第二次调用大概率已被第一次调用的递归链缓存，不会重复触发深层递归。

2. 总结规律计算 #

对于初始缓存包含1和2的场景，计算fb(n)的总调用次数：

• 非缓存调用次数：n-2次（从3到n每个数各进入一次else分支）
• 缓存命中调用次数：n-1次（递推验证：n=3时命中2次，n=4时命中3次，n=8时命中7次，符合n-1）
• 总调用次数 = (n-2) + (n-1) = 2n-3。比如n=8时，2*8-3=13，完全匹配结果。

3. 递推验证 #

• n=3：总调用次数3次（fb(3)、fb(2)、fb(1)），2*3-3=3，正确
• n=4：总调用次数5次（fb(4)、fb(3)、fb(2)、fb(2)、fb(1)），2*4-3=5，正确
• n=5：总调用次数7次，2*5-3=7，正确

内容的提问来源于stack exchange，提问作者Zercon