Question

python中解 斐波那契数递推公式不能理解？

如图,实在想不明白.....
斐波那契数列是从第三项开始,每一项都是前两项之和
公式里的n-1,和n-2的计算方式是怎样的?
n-1是不是将n的数字减一么?这里怎么算出来是n-1是n的前一项的
如果n-1是n的前一项的话第二张图片怎么解释第二张图片
n一开始为5的话,后面fact(n-1)就变成计算fact(4)了?





Answer 1

第一张图

def f(n):

 if n==1 or n==2:

  return 1

 else:

  return f(n-1)+f(n-2)

b=f(6)

print(b)

源代码(注意源代码的缩进)

第一张图是斐波那契数列的递归程序,其过程是

f(6)=f(5)+f(4)=f(4)+f(3)+f(3)+f(2)=f(3)+f(2)+f(2)+f(1)+f(2)+f(1)+f(2)

=f(2)+f(1)+f(2)+f(2)+f(1)+f(2)+f(1)+f(2)

因为f(2)=f(1)=1所以上式=1+1+1+1+1+1+1+1=8

第二张图

def fact(n):

 if n==0:

  return 1

 else:

  return n*fact(n-1)

b=fact(5)

print(b)

源代码(注意源代码的缩进)

第二张图是阶乘的递归程序,其过程是

fact(5)=5*fact(4)=5*4*fact(3)=5*4*3*fact(2)=5*4*3*2*fact(1)=5*4*3*2*1*fact(0)

因为fact(0)=1,所以上式=5*4*3*2*1*1=120

详细解释,

因为n等于5所以执行else语句返回5*fact(4)

n等于4所以执行else语句返回4*fact(3)

n等于3所以执行else语句返回3*fact(2)

n等于2所以执行else语句返回2*fact(1)

n等于1所以执行else语句返回1*fact(0)

n等于0所以执行if语句返回1

然后反向回归

fact(1)=1*1

fact(2)=2*1*1

fact(3)=3*2*1*1

fact(4)=4*3*2*1*1

fact(5)=5*4*3*2*1*1=120

Answer 2

f(5)=f(4)*f(3)
=f(3)*f(2)*f(3)
=f(2)*f(1)*f(2)*f(2)*f(1)
由于f(1）=1 f(2)=2
所以f(5)=2*1*2*2*1=8
因为数值有下限，所以递归之后会有解