递归思考Python2练习5.5

Question

这个关于ThinkPython2的练习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)

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

^{pr2}$

在函数调用自己足够的次数导致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)移动，直到该调用和所有递归调用返回为止。这个函数在结构上与您展示的功能相当，它可能会帮助您更好地了解正在发生的事情。在

Answer 2

我在下面的question中发布了一张图片，为了快速导航，这里是我的图片：