递归函数的困惑
小甲鱼老师在讲解递归函数教学视频中有以下的代码:>>> 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)会重复出现并计算,不知道我的理解对不对或哪里出错,麻烦大神指点一下,谢谢!
你理解得很正确，递归函数在计算过程中确实会出现大量的重复计算。特别是在计算斐波那契数列时，像 fibRecur(9) 这样的值会被多次调用和计算。
为了帮助你更直观地理解这一点，我用一个简单的递归树来展示 fibRecur(5) 的计算过程：
fibRecur(5)
fibRecur(5)
/ \
fibRecur(4) fibRecur(3)
/ \ / \
fibRecur(3) fibRecur(2) fibRecur(2) fibRecur(1)
/ \ \
fibRecur(2) fibRecur(1) fibRecur(1)
如你所见，fibRecur(3) 和 fibRecur(2) 都被多次计算了。当 n 更大时，这种重复计算会更加严重。
为了优化这种情况，通常我们会使用记忆化递归（Memoization）或动态规划（Dynamic Programming）的方式来避免重复计算。
这里是使用记忆化递归优化的代码示例：
def fibRecurMemo(n, memo={}):
if n == 1 or n == 2:
return 1
if n in memo:
return memo
memo = fibRecurMemo(n-1, memo) + fibRecurMemo(n-2, memo)
return memo
# 调用函数
print(fibRecurMemo(12))
这样，计算 fibRecurMemo(12) 时，每个子问题只会被计算一次，极大地提高了效率。
以上回复来自 FishC AI 小助理，如未能正确解答您的问题，请继续追问。 是的.重复了，不影响结果 的确是重复计算，但这种计算会导致效率低下 三体人的智子 发表于 2025-2-1 19:14
的确是重复计算，但这种计算会导致效率低下
衡水人？？！很累吧 某一个“天” 发表于 2025-2-2 17:03
衡水人？？！很累吧
初八参加冬令营{:10_266:}
别人十六开学 三体人的智子 发表于 2025-2-2 18:02
初八参加冬令营
别人十六开学
{:10_260:}
页:
[1]