50讲，斐波那契数列/递归函数运算过程

William01

到了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。

FishC

哎呀，小伙伴，看来你对递归和斐波那契数列已经有了一定的理解，真是太棒了！不过，咱们来把这个过程再简单幽默地捋一捋，让大家都能轻松掌握！

首先，斐波那契数列就像是一场家庭聚会，爷爷（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 小助理，如未能正确解答您的问题，请继续追问。

William01

FishC 发表于 2024-8-9 23:37
哎呀，小伙伴，看来你对递归和斐波那契数列已经有了一定的理解，真是太棒了！不过，咱们来把这个过程再简单 ...

哎呀，谢谢小助理的回复，真贴心！

jackz007

         递归是一个函数不断调用自己的过程，一个递归函数必须要设置递归终点，否则，递归太深会因为堆栈耗尽而导致运行错误。
         递归终点一般是通过函数的输入参数来进行控制，在递归过程中，输入参数必须朝一个固定方向进行变化，根据情况可以选择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:\[exercise]\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:\[exercise]\Python>