python - 无法理解 Python 2.7 中阶乘的经典递归示例

Question

我理解递归的概念，我感到困惑的地方在于流程控制。我已经看到它以两种方式呈现，一种我得到，有点，另一种我没有。示例一:

def fact(n):
    if n == 0:
        return 1
    else:
        return n * fact(n-1)

所以在这个例子中，如果我们运行 fact(3)，会发生以下情况:

fact(3) = 3*fact(3-1)`
fact(2) = 2*fact(2-1)
fact(1) = 1*fact(1-1)
fact(0) = 1

或合并:3*2*1*1 = 6

现在对于下面的内容，我被绊倒的地方是流量控制的工作原理。我的脑海里根深蒂固的是，当一个函数被调用时，其他一切都会被挂起，直到该函数完成，此时程序返回到 main。以下是我的大脑认为正在发生的事情:

def factorial(n):
    if n == 0:
        return 1
    else:
        recurse = factorial(n-1)
        result = n * recurse
        return result

我们调用阶乘(3):

factorial(3)=factorial(2)=factorial(1)=factorial(0)=1

我认为发生这种情况的原因是因为 result 是在调用之后分配的，在我看来代码永远不会到达那里，因为流控制在 result 之前挂起 main分配。我认为这个函数只是运行 n==0 的测试，直到返回 1 然后程序退出。

帮助我理解为什么我似乎无法将其概念化。

Answer 1

下面是程序流程的概要。看起来可能有点困惑，但可能会有所帮助。这里，不同的tab级别代表不同的堆栈，每一行都是程序执行的一条命令。

factorial(3)
| factorial(2)
| | factorial(1)
| | | factorial(0)
| | |   RETURNS 1
| | recurse = 1
| | result = 1 * 1 [since n=1]
| | RETURNS 1 [returning result]
| recurse = 1 [catching returned result of 1]
| result = 2 * 1 [since n=2]
| RETURNS 2 [returning result]
recurse = 2 [catching returned result of 2]
result = 3 * 2 [since n=2]
RETURNS 6 [returning result]