鱼C论坛

 找回密码
 立即注册
查看: 1905|回复: 4

[已解决]斐波那契数列递归

[复制链接]
发表于 2023-6-21 21:19:55 | 显示全部楼层 |阅读模式

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

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

x
1、递归是一种解决问题的方法,将问题分解成规模更小的问题,不断地调用自身,解决小问题,直至问题不可再分。
递归一般都是从结束条件一步一步往回计算


【我的疑问】:递归一般都是从结束条件一步一步往回计算----这句话没看懂

以下面例子为例:

# p6_8.py

def fib(n):

    if n < 1:
        print('输入有误!')
        return -1
    if n == 1 or n == 2:
        return 1
    else:
        return fib(n - 1) + fib(n - 2)

结束条件指的是fib(1) = fib(2) = 1,哪从这个结束条件一步一步往回计算其中的往回计算是什么意思?指数列往左还是数列往右?指树结构往上还是树结构往下?


2、自定义函数fib求第n个斐波那契值:采用包括0在内的完整数列即0 1 1 2 3 ……

# p6_test_.py

def fib(n):
    if n == 0: # 当n为0时返回0
        return 0
    elif n == 1: # 当n为1时返回1,实际n == 2时也是return 1,所以也可写成elif n == 1 or n == 2: 或 elif n in [1, 2]:
        return 1
    else: # 此行可以不要,但下行缩进需要提前!
        return fib(n - 1) + fib(n - 2) # 当n大于1时,用递归的方法调用函数求第n-1和第n-2个斐波那契值

n = int(input('please input:'))
print(fib(n))

语句 return fib(n-1)+fib(n-2)的意思就是向前求斐波那契值,直到n-1=1,n-2=0,因为只有第1个和第0个斐波那契值是确定的

【我的疑问】

---语句 return fib(n-1)+fib(n-2)的意思就是向前求斐波那契值,其中的向前又是什么意思?

---直到n-1=1,n-2=0,因为只有第1个和第0个斐波那契值是确定的。这句话也没看懂,n-1=1,n-2=0,和第1个和第0个斐波那契值是确定的之间有什么关系?
最佳答案
2023-6-21 21:25:39
递归是一种将问题拆分成更小的子问题来解决的方法。

在斐波那契数列例子中,使用递归的方法计算第n个斐波那契数列的值,可以看做不断把问题“向前推进”:
  • 当 n=1 或 n=2 时,斐波那契数列的值已知,直接返回 1;
  • 当 n>2 时,我们需要计算第 n-1 和第 n-2 个斐波那契数列的值,这两个问题是比原问题更简单的问题,于是我们可以用同样的方法递归解决它们;
  • 对于计算第 n-1 个斐波那契数列的值,我们需要先计算第 n-2 和第 n-3 个斐波那契数列的值;
  • 对于计算第 n-2 个斐波那契数列的值,我们需要先计算第 n-3 和第 n-4 个斐波那契数列的值;
  • ……
  • 直到计算到第 1 或 2 个斐波那契数列的值时,递归开始回溯;
  • 逐层返回每个子问题的解,最终得到第 n 个斐波那契数列的值。

在递归过程中,每一次递归调用都会把问题规模缩小,直到问题规模变得足够小,可以直接计算出来而不用递归了,这就是递归的结束条件。当递归到最后一层时,我们需要不断回溯并把每一层的结果汇总起来得到最终的答案。
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2023-6-21 21:25:39 | 显示全部楼层    本楼为最佳答案   
递归是一种将问题拆分成更小的子问题来解决的方法。

在斐波那契数列例子中,使用递归的方法计算第n个斐波那契数列的值,可以看做不断把问题“向前推进”:
  • 当 n=1 或 n=2 时,斐波那契数列的值已知,直接返回 1;
  • 当 n>2 时,我们需要计算第 n-1 和第 n-2 个斐波那契数列的值,这两个问题是比原问题更简单的问题,于是我们可以用同样的方法递归解决它们;
  • 对于计算第 n-1 个斐波那契数列的值,我们需要先计算第 n-2 和第 n-3 个斐波那契数列的值;
  • 对于计算第 n-2 个斐波那契数列的值,我们需要先计算第 n-3 和第 n-4 个斐波那契数列的值;
  • ……
  • 直到计算到第 1 或 2 个斐波那契数列的值时,递归开始回溯;
  • 逐层返回每个子问题的解,最终得到第 n 个斐波那契数列的值。

在递归过程中,每一次递归调用都会把问题规模缩小,直到问题规模变得足够小,可以直接计算出来而不用递归了,这就是递归的结束条件。当递归到最后一层时,我们需要不断回溯并把每一层的结果汇总起来得到最终的答案。
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2023-6-23 12:44:27 | 显示全部楼层
请设置最佳答案
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2023-6-23 16:10:57 | 显示全部楼层
斐波那契数列:0 1 1 2 3 5 8 13 21
向前求斐波那契值,看数列可以知道,求第N个值,需要知道N前面两个值,即N = (N-1) + (N-2) 。N-1也不知道具体值,所以会把N-1重新看做一个N,再次调用。一直当N>=2 程序会返回一个具体的值。




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

使用道具 举报

发表于 2023-6-23 21:58:14 | 显示全部楼层
第一个问题往回是回溯
比如计算fn(4)
按照函数执行就是fn(4)=fn(4-1)+fn(4-2)
开始递归
而fn(4-1)=fn(3)=fn(3-1)+fn(3-2)=fn(2)+fn(1)
而fn(2) 达到了终止条件结果为1
这递归到底了所以开始回溯 开始计算 1+fn(1)
fn(1)也到低了 现在就成了 1+1

这部分递归结束就可以运行后面的递归部分了
也就是1+1+fn(4-2)

简单理解 回溯就是执行递归函数达到了终止条件,然后开始往回运行其他需要进行的操作


第二个问题就是 fn(1) 和fn(0) 时达到了终止条件,可以直接确认值,是整个问题的最小部分。
斐波那契数列简单来说就是: 当前数是前两个数之和

举个例子
比如 第四个斐波那契数是什么呢?
我们可以用 第三个斐波那契数 + 第二个斐波那契数 来求

而 第三个斐波那契数又该怎么求呢?
我们可以用 第二个斐波那契数 + 第一个斐波那契数 来求

现在 第二个斐波那契数 和 第一个斐波那契数 我们是已知的  是确定的 我们可以直接得出答案

现在我们知道了第三个斐波那契数的值,然后我们可以开始回溯到<第四个斐波那契数是什么呢?>这个问题
第三个斐波那契数 + 第二个斐波那契数 = (第二个斐波那契数 + 第一个斐波那契数) +  第二个斐波那契数  
现在这几个数都是确定的我们就可以直接计算出结果得出答案了


如果还不理解可以看下这个青蛙跳台阶问题的视频
bilibili.com/video/BV1YP4y1o75f/?p=69
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

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

本版积分规则

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

GMT+8, 2024-11-15 03:36

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

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