算法解析（三）递归

2019-01-29 本文已影响0人书写不简单

递归的基本概念网上一大堆，这里说一下个人认为重要的点。

编写递归函数时，必须告诉它何时停止递归。正因为如此，每个递归函数都有两部分:基线条件(base case)和递归条件(recursive case)。递归条件指的是函数调用自己，而基线条件则指的是函数不再调用自己，从而避免形成无限循环。

这里提一下一个概念：调用栈（call stack）

假设你去野外烧烤，并为此创建了一个待办事项清单——一叠便条。

之前讨论数组和链表时，也有一个待办事项清单。你可将待办事项添加到该清单的任何地方，还可删除任何一个待办事项。一叠便条要简单得多:插入的待办事项放在清单的最前面;读取待办事项时，你只读取最上面的那个，并将其删除。因此这个待办事项清单只有两种操作:压入(插入)和弹出(删除并读取)。

压入和弹出.png

下面来看看如何使用这个待办事项清单。

弹出.png

这种数据结构称为栈。栈是一种简单的数据结构，刚才我们一直在使用它，却没有意识到!

计算机内部使用的栈我们称为调用栈。通过一个简单的函数了解一下；

def greet(name):
        print "hello, " + name + "!" greet2(name)
        print "getting ready to say bye..." 
        bye()

这个函数问候用户，再调用另外两个函数。这两个函数的代码如下:

def greet2(name):
        print "how are you, " + name + "?"
def bye():
        print "ok bye!"

下面详细介绍调用函数时发生的情况。
假设你调用greet("maggie")，计算机将首先为该函数调用分配一块内存。

开辟内存.png

我们来使用这些内存。变量name被设置为maggie，这需要存储到内存中。

使用内存.png
每当你调用函数时，计算机都像这样将函数调用涉及的所有变量的值存储到内存中。接下来，你打印hello, maggie!，再调用greet2("maggie")。同样，计算机也为这个函数调用分配一块内存。

函数内调用函数.png

计算机使用一个栈来表示这些内存块，其中第二个内存块位于第一个内存块上面

然后从函数调用返回。此时，栈顶的内存块被弹出。

函数返回.png

现在，栈顶的内存块是函数greet的，这意味着你返回到了函数greet。当你调用函数greet2 时，函数greet只执行了一部分

如果在当前函数里调用另外一个函数，当前函数暂停并处于未完成状态，该函数的所有变量都还在内存中。

你回到函数 greet，并从离开的地方开始接着往下执行，再调用函数bye。

函数再次调用.png

函数bye 返回之后：

函数bye返回.png

现在你又回到了函数greet。由于没有别的事情要做，你就从函数greet返回。这个栈用于存储多个函数的变量，被称为调用栈。

递归函数也使用调用栈! 下面举例说明：声明一个阶乘函数，详细分析一下调用栈

函数：

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

当首次调用为fact(3)的时候，调用栈的变化如下：

递归调用栈.jpg

函数调用栈开始返回.png

注意，每个fact调用都有自己的x变量。在一个函数调用中不能访问另一个的x变量。

使用栈虽然很方便，但是也要付出代价:存储详尽的信息可能占用大量的内存。每个函数调用都要占用一定的内存，如果栈很高，就意味着计算机存储了大量函数调用的信息。在这种情况下，你有两种选择。