浅谈递归调用栈

最近在看《算法图解》这本书，目前也在复习这些基础的算法知识，正好也可以在这里做一些总结，以加深自己的体会与理解。

说到递归，对于一个接触过计算机科学领域的人来说再熟悉不过了，从字面的意思很容易理解，但是有很多人（比如我。。。）

看似能够理解递归的思路，实则一头雾水，以至于在解题的过程中会有很多的疑问和错误。下面就来分析一下递归的工作机制。

调用栈

计算机在内部使用调用栈的栈，我们来看看是如何使用调用栈的。下面是一个函数

def great(name):

    print("hello, "+name+"!")

    great2(name)

    print("getting ready to say bye...")

    bye()

而另外两个函数：

def greet2(name):

  print("how are you, "+name+"?")

def bye():

  print("ok bye!")

开始执行时，比如调用greet("maggie"),计算机首先为该函数调用分配一块内存，将变量name设为maggie

image

接下来， 你打印hello, maggie!，再调用greet2("maggie")。同样，计算机也为这个函数调用分配一 块内存。

image

计算机使用一个栈来表示这些内存块，其中第二个内存块位于第一个内存块上面。你打印 how are you, maggie?，然后从函数调用返回。此时，栈顶的内存块被弹出。

image

现在，栈顶的内存块是函数greet的，这意味着你返回到了函数greet。当你调用函数greet2 时，函数greet只执行了一部分。这是本节的一个重要概念：调用另一个函数时，当前函数暂停 并处于未完成状态。该函数的所有变量的值都还在内存中。执行完函数greet2后，你回到函数 greet，并从离开的地方开始接着往下执行：首先打印getting ready to say bye…，再调用 函数bye。

image

在栈顶添加了函数bye的内存块。然后，你打印ok bye!，并从这个函数返回

image