时间戳

首页 > 解决方案 > 递归函数执行策略

python - 递归函数执行策略

问题描述

从运行一个基本的递归函数开始，它运行如下（完全可以预见）：

def count_to_number(n):
    print ('* Calling with n=%s' % n)
    if n == 0:
        print ('** Returning base case with n=%s' % n)
        return 0
    else:
        res = n + count_to_number(n-1)
        print ('*** Returning intermediate result with n=%s ==> %s' % (n, res))
        return res


if __name__ == '__main__':
    n = 3
    out = count_to_number(n)
    print ('**** Finished with res=%s' % out)

$ python recurse.py 
* Calling with n=3
* Calling with n=2
* Calling with n=1
* Calling with n=0
** Returning base case with n=0
*** Returning intermediate result with n=1 ==> 1
*** Returning intermediate result with n=2 ==> 3
*** Returning intermediate result with n=3 ==> 6
**** Finished with res=6

编译器（python AST 或其他）如何知道递归函数运行的“操作顺序”？例如，为什么它在评估基本情况之前不评估中间体？

我很想知道python如何“知道”在另一个结果之前评估一个结果。为什么不，例如，当它看到：

count_to_number(3) = 
                   =   3 + count_to_number(2)
                   =   3 + 2 + count_to_number(1) 
                   =   3 + 2 + 1

为什么它不从左到右评估它？

标签： pythonpython-3.xrecursion

解决方案

每次进行函数调用时，当前调用都会挂起，并创建一个新的堆栈帧，并继续执行被调用函数的主体。该功能与您当前正在执行的功能相同还是另一个功能无关紧要。

将新帧添加到调用堆栈的行为是一种隐式括号总和的方式。你的例子变成

count_to_number(3) = 
                   =   3 + count_to_number(2)
                   =   3 + (2 + count_to_number(1)) 
                   =   3 + (2 + 1)
                   =   3 + 3
                   =   6

推荐阅读