小探险家学算法

Appearance

15. 套娃（递归） ​

知识点：递归 —— 函数调用自己（"打开套娃，里面还是套娃"）

项目：阶乘 + 汉诺塔

故事开场：俄罗斯套娃 ​

你有一个俄罗斯套娃：打开它，里面是一个小一点的套娃；再打开， 更小的；一直开到最小的那个，里面才是空心的木头。

老师问："这个套娃有 5 层。第 5 层的里面，是什么？"

"是……第 4 层？不对，"你说，"打开最外面的套娃，得到的是 一个小一号的套娃——而小一号的套娃，它自己又打开， 还是套娃。一直到最小的那个，才没有套娃了。"

老师笑了："这就是递归。一件事，做一次之后，还是同一件事， 只是规模小了一号；一直小下去，直到'最小的那个'——不需要再做 就能直接回答的'出口'。"

笨办法先行：用循环，绕了一大圈 ​

先来个简单的：阶乘。5 的阶乘（写成 5!）是：

5! = 5 × 4 × 3 × 2 × 1 = 120

用循环写，很简单：

ts
function factorialLoop(n: number): number {
  let result = 1
  for (let i = 1; i <= n; i++) {
    result = result * i
  }
  return result
}

console.log(factorialLoop(5))   // 120

能跑。但你盯着它想：5! 的定义明明可以这样说——

5! 就是 5 × 4!，而 4! 就是 4 × 3!……直到 1! = 1。

"算 5 的阶乘，其实就是先算 4 的阶乘；算 4 的阶乘，就是先算 3 的阶乘…… 每一层都在做同一件事，只是数字小一号。"——这不就是套娃吗！

能不能照着这个说法直接写程序？"函数算阶乘的时候，调用'算小一号阶乘' 的函数……可那个函数，不正是它自己吗？！"

引出知识点：递归——函数调用自己 ​

可以！函数调用自己，就叫递归（recursion）：

ts
// 阶乘：5! = 5 × 4!
function factorial(n: number): number {
  if (n <= 1) {
    return 1                 // 出口：最小的套娃（1! = 1，不用再拆）
  }
  return n * factorial(n - 1)  // 打开自己：里面是 (n-1)!
}

console.log(factorial(5))    // 120

看 factorial 是怎么"拆套娃"的：

factorial(5)
= 5 × factorial(4)
= 5 × 4 × factorial(3)
= 5 × 4 × 3 × factorial(2)
= 5 × 4 × 3 × 2 × factorial(1)
= 5 × 4 × 3 × 2 × 1        ← 拆到最小的套娃，直接回答 1
= 120

递归有两样东西，缺一不可：

零件名字作用
if (n <= 1) return 1出口（基准情形）最小的套娃，不用再拆，直接回答
factorial(n - 1)递归调用打开自己，让"小一号的自己"接着拆

没有出口的递归，会永远拆下去——套娃无穷无尽，程序会栈溢出崩溃 （还记得撤销魔法章的"栈"吗？函数调用也是用栈记着的，套娃套太多， 栈就堆不下了）。

写递归的三句话：

  1. 找出"最小的套娃"（出口），直接回答；
  2. 其他情况，把它变成"小一号的自己"（递归调用）；
  3. 相信"小一号的自己"能算对——不要去手算它。

动手实现：汉诺塔——循环写不出来的难题 ​

有个古老的传说：一座庙里有三根柱子（A、B、C），A 柱上有 n 个金盘， 从大到小叠着。僧人要把所有盘子移到 C 柱，规则只有两条：

  1. 一次只能动一个盘子
  2. 大盘子永远不能压在小盘子上面（B 柱是"中转站"）

（三根柱子、大小盘子的样子，请老师帮我们在黑板上画一画—— 三个盘子，大的在下，小的在上。）

3 个盘子怎么移？你试着推演了一下，发现规则越想越乱…… "从 A 移到 C，中途还要借 B……这程序怎么写？用循环？"

试试你就知道：汉诺塔用循环写，特别绕。可它有个漂亮的递归写法：

想移 n 个盘子从 A 到 C，可以分三步——

  1. 先把上面 n−1 个盘子，从 A 移到 B（借 C 当中转）
  2. 把最底下那个大盘子，从 A 移到 C
  3. 再把 B 上的 n−1 个盘子，从 B 移到 C（借 A 当中转）

发现了吗？第 1 步和第 3 步，又是"移 n−1 个盘子"——同样的题目， 小一号！这就是递归：

ts
// 把 n 个盘子从 from 柱移到 to 柱，via 柱是中转站
function hanoi(n: number, from: string, via: string, to: string): void {
  if (n === 0) {
    return                       // 出口：没有盘子要移，直接停
  }
  hanoi(n - 1, from, to, via)    // 第一步：n-1 个盘子挪到中转柱
  console.log("把第 " + n + " 个盘子从 " + from + " 移到 " + to)
  hanoi(n - 1, via, from, to)    // 第三步：中转柱的 n-1 个盘子挪到目标柱
}

hanoi(3, "A", "B", "C")

输出：

把第 1 个盘子从 A 移到 C
把第 2 个盘子从 A 移到 B
把第 1 个盘子从 C 移到 B
把第 3 个盘子从 A 移到 C
把第 1 个盘子从 B 移到 A
把第 2 个盘子从 B 移到 C
把第 1 个盘子从 A 移到 C

3 个盘子，7 步完成。每一步都符合规则（大的不压小的）。

你盯着这 11 行代码发呆："就……就这么点？我用循环折腾半天没写出来， 递归 7 行搞定？"

这就是递归的威力：它把"怎么一步一步移"这个问题，换成了 "相信小一号的我能移好"——你只负责拆一步，剩下的交给递归。

跑起来：数一数，要移多少步？ ​

传说 64 个金盘，移完世界就毁灭。汉诺塔 n 个盘子的步数， 恰好是 2ⁿ − 1：1 个盘子 1 步，2 个 3 步，3 个 7 步，4 个 15 步……

用递归数一数（它自己也套娃：移 n 个 = 移 n−1 个 + 1 + 移 n−1 个）：

ts
// 数一数移 n 个盘子需要多少步
function hanoiSteps(n: number): number {
  if (n === 0) {
    return 0
  }
  return hanoiSteps(n - 1) + 1 + hanoiSteps(n - 1)   // 两步小一号 + 中间一步
}

console.log("3 个盘子：" + hanoiSteps(3) + " 步")
console.log("10 个盘子：" + hanoiSteps(10) + " 步")
console.log("20 个盘子：" + hanoiSteps(20) + " 步")

输出：

3 个盘子：7 步
10 个盘子：1023 步
20 个盘子：1048575 步

等等——hanoiSteps(20) 跑了 100 万次"套娃"才数出来！ 因为数 n 个盘子，它要先数两个 n−1 个盘子；数 n−1，又要数两个 n−2…… 每深一层，工作量翻一倍——这就是 2ⁿ（指数级）：每多一个盘子， 步数翻一倍。（还记得第 1 章的 O(2ⁿ) 吗？这就是它的真面目。）

其实有个一步到位的公式：2ⁿ − 1。用程序算：

ts
console.log("30 个盘子：" + (2 ** 30 - 1) + " 步")   // 1073741823
console.log("64 个盘子：" + (2 ** 64 - 1) + " 步")   // 数太大，电脑记不准了！

64 个盘子要移 2⁶⁴ − 1 ≈ 1.8 × 10¹⁹ 步——一秒移一个盘子， 要移 5800 亿年（宇宙才 138 亿岁）。

小知识：2 ** 64 算出来，电脑打印的数字末尾几位不准——还记得 第 1 章吗？电脑存大数用的是近似值。数大到一定程度， 连"精确地数一数"都成了难题，这正是我们以后要学"大数"的原因。

小挑战 ​

  1. 套娃目录：用递归打印"文件夹树"——每个文件夹里有子文件夹， 一层层打开打印（提示：写一个 showFolder(folder, depth)， 打印自己，再对每个子文件夹调用 showFolder(子文件夹, depth+1)）。
  2. 上楼梯：爬楼梯，一次可以上 1 级或 2 级。n 级楼梯有几种走法？ 提示：f(n) = f(n-1) + f(n-2)，出口是 f(1) = 1, f(2) = 2。 试试 f(10)。跑出来是不是 89？（提示：这就是著名的斐波那契数列！）
  3. 回文递归：第 3 章的 isPalindrome 是循环写的，用递归再写一遍 （提示：比较第一个和最后一个字，一样就去掉两头，检查剩下的； 出口：剩 0 个或 1 个字时一定是回文）。

课后练习 ​

第 1 题（动手题）：递归求和 ​

用递归写一个 sumTo(n)，返回 1 + 2 + ... + n 的和。 （提示：sumTo(n) = n + sumTo(n-1)，出口是 sumTo(1) = 1。 和谁很像？对了，阶乘！）

参考答案（点开查看）
ts
function sumTo(n: number): number {
  if (n <= 1) {
    return 1                 // 出口：sumTo(1) = 1
  }
  return n + sumTo(n - 1)    // 打开自己：sumTo(n) = n + sumTo(n-1)
}

console.log(sumTo(100))      // 5050

sumTo(100) 输出 5050——和第 1 章高斯的答案一样！ （高斯用公式 O(1)，这里用递归 O(n)——办法不同，答案相同。）

第 2 题（思考题）：没有出口会怎样？ ​

把 factorial 的出口（if (n <= 1) return 1）删掉，运行 factorial(5)。 会发生什么？为什么？（提示：想想"栈"——函数调用是怎么记着的。）

参考答案（点开查看）

程序会一直调用自己：factorial(5) → factorial(4) → … → factorial(0) → factorial(-1) → …，永远拆不完。

每次调用，系统都要在"调用栈"上记一笔（还记得撤销魔法章吗？）。 栈空间是有限的，拆到几万层就堆满了——程序崩溃，报错 "Maximum call stack size exceeded"（调用栈溢出）。

递归第一课：永远先写出口。 出口是递归的刹车。

第 3 题（思考题）：递归一定比循环好吗？ ​

阶乘用循环和递归都能写。那是不是"所有循环都能改递归、 递归永远更高级"？想想循环和递归各自的优点和缺点。

参考答案（点开查看）

不是。递归和循环是两种武器，各有擅长：

  • 循环：省内存（不用一层层调用栈）、速度快，适合"一步接着一步"的问题
  • 递归：代码和思路直接（照着问题的定义写）， 适合"问题里套着同一个小问题"的题（汉诺塔、文件夹树、爬楼梯）

同一道题，循环和递归常常都能解（阶乘、求和、回文都可以）。 汉诺塔这种"套娃"结构，递归几乎是最自然的写法，循环则绕到怀疑人生。

经验法则：问题里能看到"小一号的自己"，先想递归； 问题是一步一步平铺的，用循环。两个都要会——因为很多难题 （进阶篇的快速排序、回溯、动态规划！）都是递归的天下。

预告：查找与排序篇结束！你已经会找（线性、二分）、会排 （冒泡、选择、插入）、还会递归——一身的本事。 下一卷《进阶篇》要动真格的了：把递归用起来，把 O(n²) 甩在身后——快速排序、归并排序、二叉树、堆，一个一个来！