递归的基本概念网上一大堆，这里说一下个人认为重要的点。
（3.1）基本条件和递归条件
编写递归函数时，必须告诉它何时停止递归。正因为如此，每个递归函数都有两部分:基线 条件(base case)和递归条件(recursive case)。递归条件指的是函数调用自己，而基线条件则 指的是函数不再调用自己，从而避免形成无限循环。
（3.2）栈
这里提一下一个概念：调用栈（call stack）
假设你去野外烧烤，并为此创建了一个待办事项清单——一叠 便条。
之前讨论数组和链表时，也有一个待办事项清单。你可将待办事 项添加到该清单的任何地方，还可删除任何一个待办事项。一叠便条要简 单得多:插入的待办事项放在清单的最前面;读取待办事项时，你只读取 最上面的那个，并将其删除。因此这个待办事项清单只有两种操作:压入(插入)和弹出(删除并读取)。
压入和弹出.png
下面来看看如何使用这个待办事项清单。
弹出.png
这种数据结构称为栈。栈是一种简单的数据结构，刚才我们一直在使用它，却没有意识到!
（3.2.1）调用栈
计算机内部使用的栈 我们称为 调用栈。通过一个简单的函数了解一下；
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返回。这个栈用于存储多个函数的变量，被称为调用栈。
（3.3）递归调用栈
递归函数也使用调用栈! 下面举例说明：声明一个阶乘函数，详细分析一下 调用栈
函数：
def fact(x):
if x == 1:
return 1
else:
return x * fact(x-1)
当首次调用为fact(3)的时候，调用栈的变化如下：
递归调用栈.jpg
函数调用栈开始返回.png
注意，每个fact调用都有自己的x变量。在一个函数调用中不能访问另一个的x变量。
使用栈虽然很方便，但是也要付出代价:存储详尽的信息可能占用大量的内存。每个函数调 用都要占用一定的内存，如果栈很高，就意味着计算机存储了大量函数调用的信息。在这种情况 下，你有两种选择。
- 重新编写代码，转而使用
循环。 - 使用
尾递归。
小结：
- 递归指的是调用自己的函数。
- 每个递归函数都有两个条件:
基线条件和递归条件。 - 栈有两种操作:
压入和弹出。 - 所有函数调用都进入调用栈。
- 调用栈可能很长，这将占用大量的内存。
网友评论