50讲，斐波那契数列/递归函数运算过程
到了50讲了，关于递归和斐波那契数列。小甲鱼用迭代和递归的方式讲解了斐波那契数列，都不大懂。在论坛求助后大概明白了那个迭代函数，现在我自己做一下递归函数的笔记，虽然都不大懂，但是好歹思路通了。函数代码如下：
>>> def fiberRecur(n):
... if n == 1 or n == 2:
... return 1
... else:
... return fiberRecur(n-1) + fiberRecur(n-2)
...
...
>>> fiberRecur(12)
144
解析如下：
当我们调用 FiberRecur(12) 时，该函数会分解为更小的递归调用：
FiberRecur(12) 需要 FiberRecur(11) 和 FiberRecur(10)
FiberRecur(11) 需要 FiberRecur(10) 和 FiberRecur(9)
FiberRecur(10) 需要 FiberRecur(9) 和 FiberRecur(8)
FiberRecur(9) 需要 FiberRecur(8) 和 FiberRecur(7)
FiberRecur(8) 需要 FiberRecur(7) 和 FiberRecur(6)
FiberRecur(7) 需要 FiberRecur(6) 和 FiberRecur(5)
FiberRecur(6) 需要 FiberRecur(5) 和 FiberRecur(4)
FiberRecur(5) 需要 FiberRecur(4) 和 FiberRecur(3)
FiberRecur(4) 需要 FiberRecur(3) 和 FiberRecur(2)
FiberRecur(3) 需要 FiberRecur(2) 和 FiberRecur(1)
FiberRecur(2) 和 FiberRecur(1) 生成的结果是 1。
从下往上计算数值：
FiberRecur(1) = 1
FiberRecur(2) = 1
FiberRecur(3) = FiberRecur(2) + FiberRecur(1) = 1 + 1 = 2
FiberRecur(4) = FiberRecur(3) + FiberRecur(2) = 2 + 1 = 3
FiberRecur(5) = FiberRecur(4) + FiberRecur(3) = 3 + 2 = 5
FiberRecur(6) = FiberRecur(5) + FiberRecur(4) = 5 + 3 = 8
FiberRecur(7) = FiberRecur(6) + FiberRecur(5) = 8 + 5 = 13
FiberRecur(8) = FiberRecur(7) + FiberRecur(6) = 13 + 8 = 21
FiberRecur(9) = FiberRecur(8) + FiberRecur(7) = 21 + 13 = 34
FiberRecur(10) = FiberRecur(9) + FiberRecur(8) = 34 + 21 = 55
FiberRecur(11) = FiberRecur(10) + FiberRecur(9) = 55 + 34 = 89
FiberRecur(12) = FiberRecur(11) + FiberRecur(10) = 89 + 55 = 144
因此，fibreRecur(12) 生成的值为 144。
哎呀，小伙伴，看来你对递归和斐波那契数列已经有了一定的理解，真是太棒了！不过，咱们来把这个过程再简单幽默地捋一捋，让大家都能轻松掌握！
首先，斐波那契数列就像是一场家庭聚会，爷爷（F(1)）和奶奶（F(2)）都来参加，他们都有1个小孩。接下来，家庭聚会的人数就会像斐波那契数列一样增长：每次新生的小孩都是由他俩的孩子组合而成（也就是前面两个孩子的数量相加）。所以，想要知道第n个孩子有多少人，就要去找他们前面的两个孩子一起“凑份子”。
### 递归的思路
在你的代码中：
def fiberRecur(n):
if n == 1 or n == 2:
return 1
else:
return fiberRecur(n-1) + fiberRecur(n-2)
这段代码就像是一个非常热情的“聚会策划者”。每当你问他第n个孩子的数量，他就会说：“让我去问问第(n-1)个和第(n-2)个孩子。” 然后继续这样询问下去，直到问到1号和2号孩子（他们都是1个）。
### 分解过程
调用 `fiberRecur(12)` 就好比你在派对上找一个特别的12号孩子，结果发现为了找到这个小家伙，你得先看看11号和10号是怎么说的；然后11号又回去找10号和9号……这就像打开了一层层的洋葱，每一层都是对更小问题的追问，直到找到最基本的答案（1和1）。
### 从下往上计算
然后你就开始从小孩的回答往上算：
- F(2) = 1
- F(3) = F(2) + F(1) = 1 + 1 = 2
- F(4) = F(3) + F(2) = 2 + 1 = 3
- ……
一直到你终于算出F(12)的值，144，哇塞，12号孩子长得可真不错！
### 性能考虑
但是有一个问题，每次你问孩子的数量，都会回去问前面的孩子，这样反复询问会导致很多重复计算（就像派对上，大家一直问“你见过几号吗？”，造成信息混乱）。如果想提高效率，可以考虑使用迭代方法或者记忆化递归，这样就不会每次都重复询问啦。
总之，递归就像是一场愉快的聚会，而斐波那契数列则是在这个聚会上快速成长的小朋友们。希望你可以像斐波那契数列一样，越来越聪明，越来越好玩！加油！
以上回复来自 FishC AI 小助理，如未能正确解答您的问题，请继续追问。 FishC 发表于 2024-8-9 23:37
哎呀，小伙伴，看来你对递归和斐波那契数列已经有了一定的理解，真是太棒了！不过，咱们来把这个过程再简单 ...
哎呀，谢谢小助理的回复，真贴心！ 本帖最后由 jackz007 于 2024-8-10 22:15 编辑
递归是一个函数不断调用自己的过程，一个递归函数必须要设置递归终点，否则，递归太深会因为堆栈耗尽而导致运行错误。
递归终点一般是通过函数的输入参数来进行控制，在递归过程中，输入参数必须朝一个固定方向进行变化，根据情况可以选择i逐渐减小或者增大，当变化达到一定的数值时，递归终止。
以本例为例，输入参数 n 在递归中是逐渐减小的过程，当 n 大于 2 的时候，会继续递归，否则，当 n = 1 或 n = 2 的时候，递归到达终点，开始进入返回过程，并逐级执行递归调用语句后面的语句，直到递归调用全部返回。
考察、运行一下这个代码可能会有助于加深对递归函数的理解
def recurse(n , c):
if c < 11:
print('第【%2d】层：进入 n = %3d' % (c , n)) # 进入过程执行
recurse(n + 1 , c + 1) # 递归
print('第【%2d】层：退出 n = %3d' % (c , n)) # 退出过程执行
else :
print('【终点】：c = %2d , n = %3d' % (c , n)) # 递归终点
recurse(33 , 0)
运行实况：
D:\\Python>python recurse.py
第【 0】层：进入 n =33
第【 1】层：进入 n =34
第【 2】层：进入 n =35
第【 3】层：进入 n =36
第【 4】层：进入 n =37
第【 5】层：进入 n =38
第【 6】层：进入 n =39
第【 7】层：进入 n =40
第【 8】层：进入 n =41
第【 9】层：进入 n =42
第【10】层：进入 n =43
【终点】：c = 11 , n =44
第【10】层：退出 n =43
第【 9】层：退出 n =42
第【 8】层：退出 n =41
第【 7】层：退出 n =40
第【 6】层：退出 n =39
第【 5】层：退出 n =38
第【 4】层：退出 n =37
第【 3】层：退出 n =36
第【 2】层：退出 n =35
第【 1】层：退出 n =34
第【 0】层：退出 n =33
D:\\Python>
页:
[1]