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’的幂，我可以理解这个递归，因为在一行中只有一个递归调用，所以在y==0之前，它会调用自己。同样，所有的结果不都应该是'1‘吗?因为当y==0时，最后执行的命令是'return 1’，因此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

简短的回答

每次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)时，它终于达到了一个基本情况。它计算返回1的fibonacci(1)，然后第一次可以继续到fibonacci()调用的+ fibonacci(number-2)部分。fibonacci(0)返回0，然后让fibonacci(2)返回1。

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

这个过程会一直持续下去，直到所有东西都被评估完毕，并且fibonacci(4)可以返回3。

要查看整个评估过程，请遵循下图中的箭头：

​

​

Answer 3

做'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