鱼C论坛

 找回密码
 立即注册
查看: 147|回复: 3

[已解决]递归函数计算

[复制链接]
发表于 2024-8-1 16:50:50 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能^_^

您需要 登录 才可以下载或查看,没有账号?立即注册

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


fibRecur(12)

--------------------------------------------------------
代码如上,哪位大神能分析一下递归函数计算过程吗?
最佳答案
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 小助理,如未能正确解答您的问题,请继续追问。
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 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 小助理,如未能正确解答您的问题,请继续追问。
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2024-8-1 18:03:17 | 显示全部楼层

这递归结构很简单,那不用拿个那么大的数来写,因为前面都是重复的过程
执行 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

想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2024-8-1 20:28:29 | 显示全部楼层
你可以把下一层递归看作已经算好的值, 然后就行了
你可以模拟一个 Fib 数组, 然后模拟他向前跳的过程, 如果位置变成小于等于 2 就原路返回
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

小黑屋|手机版|Archiver|鱼C工作室 ( 粤ICP备18085999号-1 | 粤公网安备 44051102000585号)

GMT+8, 2024-12-22 23:35

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

快速回复 返回顶部 返回列表