本章内容

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

小结

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

思考

假设递归函数没有基线条件会是什么情况？

• 函数调用都会被压入调用栈，如果没有基线条件，则递归函数一直调用自己，这使得调用栈只压入而不弹出，导致操作系统分配给程序的内存被耗尽，最终程序崩溃。

3.1 递归、循环

盒子里的钥匙

问题背景：钥匙可能在盒子里，但是这个盒子里可能还有其他盒子，每个盒子都是如此。

如果使用循环，程序的性能可能更高；如果使用递归，程序可能更容易理解；如何选择要看什么对你来说更重要。

方法1 while

方法2 递归

3.2 基线条件和递归条件

英文名base case , recursive case；递归条件指的是函数调用自己，而基线条件指的是函数不在调用自己，从而避免形成无限循环。

# 倒计时的函数
def countdown(i):
    print(i)
    if i <= 1:     <--------- base case
        return 
    else:          <--------- recursive case  
        countdown(i-1)

3.3 栈

调用栈（ call stack ）与递归的理解密切相关。

调用另一个函数时，当前函数暂停并处于未完成状态。该函数的所有变量的值都在内存中。当被调用的函数执行完毕后，回到调用它的函数，并从这个函数离开的地方继续向下执行。

用递归计算阶乘

# 计算阶乘
def fact(x):
    if x==1:
        return 1
    else:
        return x*fact(x-1)

缺点

使用栈虽然方便，但是内存代价高。有两种解决方式：

• 重新编写，采用循环结构
• 使用尾递归，但可惜，这并不是被所有语言都支持。