递归函数的困惑

LEEFEI571

小甲鱼老师在讲解递归函数教学视频中有以下的代码:

>>> def fibRecur(n):
...     if n == 1 or n == 2:
...         return 1
...     else:
...         return fibRecur(n-1) + fibRecur(n-2)
...
>>> fibRecur(12)
144

     当输入n为12时,n不满足if n==1 or n== 2的条件,进入到else语句部分,即fibRecur(n-1) + fibRecur(n-2), 此时变为fibRecur(12-1) + fibRecur(12-2),即fibRecur(11) + fibRecur(10),这时候应该重新调用fibRecur函数自身,因为此时n已分别变为11和10了, n仍不满足if n==1 or n== 2的条件,还是进入到else语句部分,这里是不是应该变为fibRecur(11-1) + fibRecur(11-2)+ fibRecur(10-1) + fibRecur(10-2)啊?即fibRecur(10) + fibRecur(9)+ fibRecur(9) + fibRecur(8).
     如果我的理解没有错的话,那这里的fibRecur(9)会重复出现并计算,不知道我的理解对不对或哪里出错,麻烦大神指点一下,谢谢!

FishC

你理解得很正确，递归函数在计算过程中确实会出现大量的重复计算。特别是在计算斐波那契数列时，像 fibRecur(9) 这样的值会被多次调用和计算。

为了帮助你更直观地理解这一点，我用一个简单的递归树来展示 fibRecur(5) 的计算过程：

fibRecur(5)

1.                      fibRecur(5)
   
2.                    /            \
   
3.           fibRecur(4)            fibRecur(3)
   
4.           /       \              /       \
   
5.     fibRecur(3) fibRecur(2) fibRecur(2) fibRecur(1)
   
6.     /         \          \
   
7. fibRecur(2) fibRecur(1) fibRecur(1)

复制代码

如你所见，fibRecur(3) 和 fibRecur(2) 都被多次计算了。当 n 更大时，这种重复计算会更加严重。

为了优化这种情况，通常我们会使用记忆化递归（Memoization）或动态规划（Dynamic Programming）的方式来避免重复计算。

这里是使用记忆化递归优化的代码示例：

1. 
   
2. def fibRecurMemo(n, memo={}):
   
3.     if n == 1 or n == 2:
   
4.         return 1
   
5.     if n in memo:
   
6.         return memo[n]
   
7.    
   
8.     memo[n] = fibRecurMemo(n-1, memo) + fibRecurMemo(n-2, memo)
   
9.     return memo[n]
   
10. 
    
11. # 调用函数
    
12. print(fibRecurMemo(12))
    

复制代码

这样，计算 fibRecurMemo(12) 时，每个子问题只会被计算一次，极大地提高了效率。

以上回复来自 FishC AI 小助理，如未能正确解答您的问题，请继续追问。

某一个“天”

是的.重复了，不影响结果

三体人的智子

的确是重复计算，但这种计算会导致效率低下

某一个“天”

三体人的智子 发表于 2025-2-1 19:14
的确是重复计算，但这种计算会导致效率低下

衡水人？？！很累吧

三体人的智子

某一个“天” 发表于 2025-2-2 17:03
衡水人？？！很累吧

初八参加冬令营
别人十六开学

某一个“天”

三体人的智子 发表于 2025-2-2 18:02
初八参加冬令营
别人十六开学