[已解决]递归函数计算

XX学Python

def fibRecur(n):
    if n == 1 or n == 2:
        return 1
    else:
        return fibRecur(n - 1) + fibRecur(n - 2)


fibRecur(12)

--------------------------------------------------------
代码如上，哪位大神能分析一下递归函数计算过程吗？

最佳答案

月排行榜 / 总排行榜

FishC

2024-8-1 16:53:12

当然可以！递归就像是给你一个“迷宫”，你需要根据某些规则进出，直到找到出口。咱们来分析一下这个 `fibRecur` 函数，它的任务是计算斐波那契数列：前两个数字都是1，从第三个数字开始，每个数字都是前两个数字的和。

### 1. 初始状态
你调用 `fibRecur(12)`，这就像是让你从第12个走到第1个，通过一路回顾之前的每一步。

### 2. 递归过程
当 `n` 是 12 时，程序会看到 `n` 不等于 1 或 2，于是它就会去掉最后两个椅子，分别计算 `fibRecur(11)` 和 `fibRecur(10)`。

这是一个递归的过程，每一次都在问，“前面的数字是多少？”然后它会继续拆分下去。

- **fibRecur(12)**
  - = fibRecur(11) + fibRecur(10)
  
接着又会继续拆分 `fibRecur(11)` 和 `fibRecur(10)`：

- **fibRecur(11)**
  - = fibRecur(10) + fibRecur(9)

- **fibRecur(10)**
  - = fibRecur(9) + fibRecur(8)

以此类推，你会发现程序像个“倒叙”录音机一样，不断地把数字拆解，直到最底层的 1 和 2，这些就是它的基础情况。

### 3. 基础情况
- 当 `n` 是 1 或 2 时，直接返回 1，这是它知道的最基本的事实，就如同小孩子知道手里有的玩具数目。

### 4. 汇聚结果
一旦到达基础情况，开始逐步返回结果。我们假设一下返回的路径：

- fibRecur(2) = 1
- fibRecur(1) = 1

那么：

- fibRecur(3) = 1 + 1 = 2
- fibRecur(4) = 1 + 2 = 3
- fibRecur(5) = 2 + 3 = 5
- fibRecur(6) = 3 + 5 = 8
- fibRecur(7) = 5 + 8 = 13
- fibRecur(8) = 8 + 13 = 21
- fibRecur(9) = 13 + 21 = 34
- fibRecur(10) = 21 + 34 = 55
- fibRecur(11) = 34 + 55 = 89
- fibRecur(12) = 55 + 89 = 144

最后，`fibRecur(12)` 的结果就是 144，而那就是第12个斐波那契数！

### 小总结
这个递归函数就像是在家里找人，先要从门口开始，慢慢向里走，最后再把每个人的名字都记下来，回头再跟你报告谁在家里。虽然可能走得有点慢（因为很多重复），但最终还是能找到答案的，哈哈！希望我的解释能帮助你理解递归的魅力！

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

跳转到最佳答案楼层

FishC

当然可以！递归就像是给你一个“迷宫”，你需要根据某些规则进出，直到找到出口。咱们来分析一下这个 `fibRecur` 函数，它的任务是计算斐波那契数列：前两个数字都是1，从第三个数字开始，每个数字都是前两个数字的和。

### 1. 初始状态
你调用 `fibRecur(12)`，这就像是让你从第12个走到第1个，通过一路回顾之前的每一步。

### 2. 递归过程
当 `n` 是 12 时，程序会看到 `n` 不等于 1 或 2，于是它就会去掉最后两个椅子，分别计算 `fibRecur(11)` 和 `fibRecur(10)`。

这是一个递归的过程，每一次都在问，“前面的数字是多少？”然后它会继续拆分下去。

- **fibRecur(12)**
  - = fibRecur(11) + fibRecur(10)
  
接着又会继续拆分 `fibRecur(11)` 和 `fibRecur(10)`：

- **fibRecur(11)**
  - = fibRecur(10) + fibRecur(9)

- **fibRecur(10)**
  - = fibRecur(9) + fibRecur(8)

以此类推，你会发现程序像个“倒叙”录音机一样，不断地把数字拆解，直到最底层的 1 和 2，这些就是它的基础情况。

### 3. 基础情况
- 当 `n` 是 1 或 2 时，直接返回 1，这是它知道的最基本的事实，就如同小孩子知道手里有的玩具数目。

### 4. 汇聚结果
一旦到达基础情况，开始逐步返回结果。我们假设一下返回的路径：

- fibRecur(2) = 1
- fibRecur(1) = 1

那么：

- fibRecur(3) = 1 + 1 = 2
- fibRecur(4) = 1 + 2 = 3
- fibRecur(5) = 2 + 3 = 5
- fibRecur(6) = 3 + 5 = 8
- fibRecur(7) = 5 + 8 = 13
- fibRecur(8) = 8 + 13 = 21
- fibRecur(9) = 13 + 21 = 34
- fibRecur(10) = 21 + 34 = 55
- fibRecur(11) = 34 + 55 = 89
- fibRecur(12) = 55 + 89 = 144

最后，`fibRecur(12)` 的结果就是 144，而那就是第12个斐波那契数！

### 小总结
这个递归函数就像是在家里找人，先要从门口开始，慢慢向里走，最后再把每个人的名字都记下来，回头再跟你报告谁在家里。虽然可能走得有点慢（因为很多重复），但最终还是能找到答案的，哈哈！希望我的解释能帮助你理解递归的魅力！

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

Twilight6

这递归结构很简单，那不用拿个那么大的数来写，因为前面都是重复的过程

执行 fibRecur(5) -> else -> return fibRecur(4) + fibRecur(3)   

        进入递归： fibRecur(4) -> else -> fibRecur(3) + fibRecur(2)

                进入递归： fibRecur(3) -> else ->  fibRecur(2) + fibRecur(1)

                        进入递归： fibRecur(2) -> if ->  
                        
                                退出 fibRecur(2) 递归，fibRecur(2) = 1

                        进入递归： fibRecur(1) -> if ->  
                        
                                退出 fibRecur(1) 递归，fibRecur(1) = 1
                
                        返回：fibRecur(2) + fibRecur(1) = 1 + 1 = 2 
        
                        退出 fibRecur(3) 递归，fibRecur(3) = 2

                进入递归： fibRecur(2) -> if ->  

                        退出 fibRecur(2) 递归，fibRecur(2) = 1
        
                返回：fibRecur(3) + fibRecur(2) = 2 + 1 = 3

                退出 fibRecur(4) 递归，fibRecur(4) = 3

        进入递归： fibRecur(3) -> else -> fibRecur(2) + fibRecur(1)

                进入递归： fibRecur(2) -> if ->  
                
                        退出 fibRecur(2) 递归，fibRecur(2) = 1

                进入递归： fibRecur(1) -> if ->  
                
                        退出 fibRecur(1) 递归，fibRecur(1) = 1
        
                返回：fibRecur(2) + fibRecur(1) = 1 + 1 = 2 

                退出 fibRecur(3) 递归，fibRecur(3) = 2

        返回：fibRecur(4) + fibRecur(3) = 3 + 2 = 5

        退出 fibRecur(5) 递归，fibRecur(5) = 5

柿子饼同学

你可以把下一层递归看作已经算好的值, 然后就行了
你可以模拟一个 Fib 数组, 然后模拟他向前跳的过程, 如果位置变成小于等于 2 就原路返回