Python字典递归函数计算存疑：myfunc(6, {1:1,2:2})为何返回13而非8？

你遇到的问题核心是对递归的分支展开逻辑理解有误——你把递归调用当成了线性的链式推导，但实际上每个myfunc(n)的两个递归分支（myfunc(n-1)和myfunc(n-2)）都会被完整计算，而不是只展开其中一个。

我们来一步步拆解myfunc(6, {1:1,2:2})的实际执行过程：

• 计算myfunc(6,d)：6不在字典里，所以返回myfunc(5,d) + myfunc(4,d)
• 先算myfunc(5,d)：5不在字典里，返回myfunc(4,d) + myfunc(3,d)
• 再算myfunc(4,d)：4不在字典里，返回myfunc(3,d) + myfunc(2,d)
• 计算myfunc(3,d)：3不在字典里，返回myfunc(2,d) + myfunc(1,d)，而myfunc(2,d)=2，myfunc(1,d)=1，所以myfunc(3,d)=2+1=3
• 回到myfunc(4,d)：代入myfunc(3,d)=3和myfunc(2,d)=2，得到3+2=5
• 回到myfunc(5,d)：代入myfunc(4,d)=5和myfunc(3,d)=3，得到5+3=8
• 最后回到myfunc(6,d)：代入myfunc(5,d)=8和myfunc(4,d)=5，得到8+5=13

而你的错误在于，你把递归过程简化成了类似myfunc(6) → myfunc(5) → myfunc(4) → myfunc(3)的线性链，只累加了myfunc(2)的值，但实际上每个步骤的两个分支都要计算，比如myfunc(3)是2+1，myfunc(4)是3+2，这些值都会被代入到上层的调用中，最终总和是13而不是8。

简单来说，你的预期忽略了递归中每个节点的两个子调用都会被执行并返回结果，而不是只沿着一个分支走到底。

内容的提问来源于stack exchange，提问作者Alissa L.