递归

  • 递归
  • 基线条件和递归条件
  • 调用栈
  • 递归调用栈

递归

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

方法一（循环）：创建一个要查找的盒子堆，从盒子堆取出一个盒子，在里面找。如果找到的是盒子，加入盒子堆；如果找到钥匙，大功告成。

def look_for_key(main_box):
    pile = main_box.make_a_pile_to_look_through()
    while pile is not empty:
        box = pile.grab_a_box()
        for item in box:
            if item.is_a_box():
                pile.append(item)
            elif item.is_a_key():
                print "found the key!"

方法二（递归）：函数调用自己。

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!"

两种方法作用相同，但递归的解决方案更清晰。递归只是让解决方案更清晰，没有性能上的优势。实际上，在有些情况下使用循环的性能更好。

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

基线条件和递归条件

编写递归函数时，很容易出错导致无限循环。每个递归函数都有两部分：

  • 基线条件（base case）：函数不再调用自己，避免无限循环
  • 递归条件（recursive case）：函数调用自己
def countdown(i):
    print i
    if i <= 0:        # 基线条件
        return
    else:             # 递归条件
        countdown(i - 1)

调用栈

计算机在内部使用被称为调用栈的栈。栈是一种简单的数据结构，只有两种操作：压入（插入）和弹出（删除并读取）。

调用栈的工作原理：假设有一个函数 greet，它调用了 greet2 和 bye：

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") 时：

  1. 计算机为 greet 调用分配一块内存，存储变量 name 的值
  2. 打印 hello, maggie!，再调用 greet2("maggie")
  3. 计算机为 greet2 调用分配另一块内存，放在第一块上面（栈顶）
  4. 打印 how are you, maggie?，从 greet2 返回，栈顶内存块弹出
  5. 回到 greet，打印 getting ready to say bye...，调用 bye()
  6. bye 的内存块被压入栈顶
  7. 打印 ok bye!，从 bye 返回，弹出
  8. 回到 greet，没有别的事情，从 greet 返回

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

递归调用栈

递归函数也使用调用栈。来看阶乘函数 fact(x)，其中 5! = 5 * 4 * 3 * 2 * 1：

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

调用 fact(3) 时，调用栈的变化：

  1. 调用 fact(3)，但 fact(3) 需要 fact(2) 的结果，暂停
  2. 调用 fact(2)，需要 fact(1) 的结果，暂停
  3. 调用 fact(1)，返回 1
  4. fact(2) 恢复：2 * 1 = 2，返回 2
  5. fact(3) 恢复：3 * 2 = 6，返回 6

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

使用栈的代价：存储详尽的信息可能占用大量内存。每个函数调用都要占用一定的内存，如果栈很高，就意味着计算机存储了大量函数调用的信息。这时有两种选择：

  • 重新编写代码，转而使用循环
  • 使用尾递归（高级递归主题，并非所有语言都支持）

小结

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