斐波那契递归，为什么 fib(2) 打印两个？

Question

def fib(x):
  if x == 0 or x == 1:
   return 1
  else:
   return fib(x-1) + fib(x-2)

print (fib(2))

我的逻辑是：

1st fib(2-1)+fib(2-2) return fib(1) 
2st fib(1) return 1 ; 
3rd print 1

谁能告诉我我的想法哪里错了？

Answer 1

你的逻辑在这里有问题

 if x == 0 or x == 1:
       return 1

因此

    1st fib(2-1) + fib(2-2) ; 
subdivide into fib(1) + fib(0);
    2nd fib(1) return 1 + fib(0) return 1;
    3rd 1+1 = 2;
    print 2;

你的if语句状态if x== 0 OR x == 1: return 1;

Answer 2

斐波那契数列的前5项如下：

您的代码 return 是前 5 个术语的系列：

你的函数没有 return 正确值的原因是因为这个 if 语句：

if x == 0 or x == 1:
    return 1

这当然是完全错误的。为了获得正确的数字，您必须像这样修改代码：

def fib(x):
    if x == 0:
        return 0
    elif x == 1 or x == 2:
        return 1
    else:
        return fib(x-1) + fib(x-2)

如果参数 x 为 0，则更正函数 returns 0，如果参数为 1 或 2，则为 1。

Fibonacci Recursive, why fib(2) print two?