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

lzb1001

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个斐波那契值是确定的之间有什么关系？

最佳答案

月排行榜 / 总排行榜

sfqxx

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 个斐波那契数列的值。
  

在递归过程中，每一次递归调用都会把问题规模缩小，直到问题规模变得足够小，可以直接计算出来而不用递归了，这就是递归的结束条件。当递归到最后一层时，我们需要不断回溯并把每一层的结果汇总起来得到最终的答案。

跳转到最佳答案楼层

sfqxx

递归是一种将问题拆分成更小的子问题来解决的方法。

在斐波那契数列例子中，使用递归的方法计算第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 个斐波那契数列的值。
  

在递归过程中，每一次递归调用都会把问题规模缩小，直到问题规模变得足够小，可以直接计算出来而不用递归了，这就是递归的结束条件。当递归到最后一层时，我们需要不断回溯并把每一层的结果汇总起来得到最终的答案。

sfqxx

请设置最佳答案

Stubborn

斐波那契数列：0 1 1 2 3 5 8 13 21
向前求斐波那契值，看数列可以知道，求第N个值，需要知道N前面两个值，即N = (N-1) + (N-2) 。N-1也不知道具体值，所以会把N-1重新看做一个N，再次调用。一直当N>=2 程序会返回一个具体的值。

roberte

第一个问题往回是回溯
比如计算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