python - 递归 Think Python 2 练习 5.5

Question

有关 Think Python 2 练习 5.5 的问题已 asked and answered already ，但我还是不明白这个功能是如何工作的。这是有问题的函数:

def draw(t, length, n):
    if n == 0:
        return
    angle = 50
    t.fd(length*n)
    t.lt(angle)
    draw(t, length, n-1)
    t.rt(2*angle)
    draw(t, length, n-1)
    t.lt(angle)
    t.bk(length*n)

我在这里看到一个递归循环:

def draw(t, length, n):
    if n == 0:
        return
    angle = 50
    t.fd(length*n)
    t.lt(angle)
    draw(t, length, n-1)

在函数调用自身足够多的次数导致 n == 0 后，它如何进入下一步，即 t.rt(2*angle)？一旦 n == 0，函数不应该返回 None 并简单地结束吗？如果不是，又要回到哪里？下次调用自身时，同样的事情会再次发生，然后该函数在满足状态 n == 0 后很长时间内继续执行工作(两次!)。我显然在这里遗漏了一个关键概念，并且希望任何人都能就这个主题提供任何启发。先谢谢了~

Answer 1

return 语句将程序的执行返回到调用返回函数的行。

如果您不熟悉调用堆栈是什么，请将其视为函数堆栈 - 每当调用某些内容时，它就会被放置在堆栈顶部，这就是正在运行的内容。当它返回时，它会从堆栈中删除，因此调用它的函数(堆栈中下面的一个)现在位于顶部，因此执行会再次开始。

当 n == 0 (所以这是你的基本情况)时，该特定函数将返回，因此一旦它的递归调用 draw(t, length, n-1) - 因此，它的后续的递归调用，因为在它们完成之前它不会完成执行 - 到达该点，它将移至下一行。

采用更简单的函数 foo(sum, n) 代替:

def foo(sum, n):
    if (n == 0):
        return sum
    sum += foo(sum, n-1)
    sum /= 2
    return foo(sum, n-1)

无论何时调用它，它都不会从 sum += foo(sum, n-1) 移动，直到该调用和所有递归调用返回为止。该函数在结构上与您展示的函数相当，它可能会帮助您更好地可视化正在发生的事情。