递归

• 学习递归。递归是很多算法都使用的一种编程方法
• 学习如何将问题分成基线条件和递归条件

递归

假设你在祖母的阁楼中翻箱倒柜，发现了一个上锁的神秘手提箱。祖母告诉你，钥匙很可能在下面这个盒子里。这个盒子里有盒子，而盒子里的盒子又有盒子。钥匙就在某个盒子中。

def look_for_key(box):
 for item in box:
    if item.is_a_box():
        look_for_key(item) ←------递归！
    elif item.is_a_key():
        print "found the key!"

递归只是让解决方案更清晰，并没有性能上的优势。实际上，在有些情况下，使用循环的性能更好。我很喜欢Leigh Caldwell在Stack Overflow上说的一句话：“如果使用循环，程序的性能可能更高；如果使用递归，程序可能更容易理解。如何选择要看什么对你来说更重要。”

基线条件和递归条件

由于递归函数调用自己，因此编写这样的函数时很容易出错，进而导致无限循环。

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

栈

栈是一种简单的数据结构，刚才我们一直在使用它，却没有意识到！计算机在内部使用被称为调用栈的栈。

递归函数也使用调用栈！栈在递归中扮演着重要角色。

使用循环方法时，你创建一个待查找的盒子堆，因此你始终知道还有哪些盒子需要查找。但使用递归方法时，没有盒子堆。

“盒子堆”存储在了栈中！这个栈包含未完成的函数调用，每个函数调用都包含还未检查完的盒子。使用栈很方便，因为你无需自己跟踪盒子堆——栈替你这样做了。

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

• 重新编写代码，转而使用循环。
• 使用尾递归。这是一个高级递归主题.

小结

• 递归指的是调用自己的函数。
• 每个递归函数都有两个条件：基线条件和递归条件。
• 栈有两种操作：压入和弹出。
• 所有函数调用都进入调用栈。
• 调用栈可能很长，这将占用大量的内存。