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(number-1)'是否完成所有递归直到达到'1'然后它与'fibonacci(number-2)'一样并添加它们？

为了比较,下面的递归函数用于将数字"x"提升为幂'y',我可以理解递归,def函数调用自身直到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

简答

每次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),它可以进展到evaluate fibonacci(number-2)(fibonacci(1)).

此过程将继续,直到所有内容都已评估并fibonacci(4)可以返回3.

要查看整个评估的进展情况,请按照此图中的箭头操作:

Answer 2

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

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

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