Python中的递归函数

Question

考虑一下Python中的这个基本递归：

def fibonacci(number):
    if number == 0: return 0
    elif number == 1:
        return 1
    else:
        return fibonacci(number-1) + fibonacci(number-2)

根据Fibonacci级数的（n-1）+（n-2）函数，这是有意义的。

Python如何执行包含另一个不在同一代码行内但在同一代码行内的递归？“finobacci（数字-1）”是否完成所有递归，直到它达到“1”，然后它对“fibonacci（数字-2）”执行相同的操作并添加它们？

为了进行比较，下面的递归函数将数字“x”提升为幂“y”，我可以理解递归，def power调用自身直到y==0，因为在一行中只有一个递归调用。仍然不应该所有结果都是“1”，因为上次执行的命令是“return 1”，当y==0时，因此不返回x？

def power(x, y):
    if y == 0:
        return 1
    else:
        return x*power(x, y-1)

Answer 1

在表达式fibonacci(number-1) + fibonacci(number-2)中，第一个函数调用必须在调用第二个函数调用之前完成。

所以，第一次调用的整个递归堆栈必须在第二次调用开始之前完成。

Answer 2

does the 'finobacci(number-1)' completes all the recursion until it reaches '1' and then it does the same with 'fibonacci(number-2)' and add them?

是的，完全正确。换句话说，下面

return fibonacci(number-1) + fibonacci(number-2)

相当于

f1 = fibonacci(number-1)
f2 = fibonacci(number-2)
return f1 + f2

Answer 3

简短的回答

每次Python“看到”fibonacci()时，它都会进行另一个函数调用，并且在完成该函数调用之前不会进一步进行。

示例

所以假设它在计算fibonacci(4)。

一旦到达return fibonacci(number-1) + fibonacci(number-2)行，它就会“看到”调用fibonacci(number-1)。

所以现在它运行fibonacci(3)-它还没有看到fibonacci(number-2)。要运行fibonacci(3)，它必须找出fibonacci(2)+fibonacci(1)。再次，它运行它看到的第一个函数，这次是fibonacci(2)。

现在，当运行fibonacci(2)时，它终于到达一个基本情况。它计算fibonacci(1)，返回1，然后，它第一次可以继续执行+ fibonacci(number-2)调用的fibonacci()部分。fibonacci(0)返回0，然后让fibonacci(2)返回1。

既然fibonacci(3)已经获得了从fibonacci(2)返回的值，那么它可以继续计算fibonacci(number-2)（fibonacci(1)）。

此过程将继续，直到所有内容都已计算完毕，并且fibonacci(4)可以返回3。

要查看整个评估过程，请按照此图中的箭头操作：