Python中的递归函数

Question

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

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

根据斐波那契数列的（n-1）（n-2）函数，这是有道理的。

Python如何执行包含另一个递归的递归，这个递归不在同一代码行内，而是在同一代码行内？“finobacci(number-1)”是否完成所有递归，直到它到达“1”，然后它对“fibonacci(number-2)”做同样的事情，并将它们相加？

作为比较，下面的递归函数将一个数“x”提升为“y”的幂，我可以理解这个递归，def power调用它自己直到y==0，因为在一行中只有一个递归调用。既然当y==0时执行的最后一个命令是“return 1 ”,因此x没有被返回，那么所有的结果不都应该是“1”吗？

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

Answer 1

“finobacci（number-1）”是否完成所有递归，直到它达到“1”，然后它与“fibonacci（number-2）”做同样的事情并将它们相加？

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

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

相当于

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

Answer 2

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

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

Answer 3

每次Python“看到”fibonacci（），它都会进行另一次函数调用，直到完成该函数调用为止。

假设它正在评估fibonacci（4）。

一旦它到达行< code > return Fibonacci(number-1)Fibonacci(number-2)，它就“看到”调用< code>fibonacci(number-1)。

所以现在它运行的是斐波那契（3）-它还没有看到菲波那奇（2号）。要运行fibonacci（3），它必须计算出斐波那契（2）和斐波那奇（1）。同样，它运行它看到的第一个函数，这一次是斐波那契（2）。

现在，当＜code＞fibonacci（2）fibonacci（1），返回1，然后第一次可以继续执行fibonac契（）调用的斐波那契（数字-2）部分fibonacci（0）返回0，然后让斐波那契（2）返回1。

现在< code>fibonacci(3)已经获得了从< code>fibonacci(2)返回的值，它可以继续计算< code > Fibonacci(number-2)(< code > Fibonacci(1))。

这个过程一直持续到一切都被评估， 斐波那契（4）可以返回 3.

若要查看整个评估的进展情况，请按照下图中的箭头进行操作：