递归如何工作

拆解递归

我们来看看递归如何神奇地求出任意数的阶乘。代码如下：

(define (factorial n)
  (if (= n 0)
      1
      (* n (factorial (- n 1)))))

factorial 在 n 为 0 时返回 1，否则返回 n 与 n - 1 的阶乘之积。

每个递归过程都会使用条件表达式，并且需要两种情况：

• 基例（base case）：这种情况结束递归。递归过程的任何输入最终都会到达基例。
• 递归例（recursive case）：这种情况减小问题的规模。递归例总会尝试把问题变小，直到到达基例。

一个递归过程中可以有多个基例或多个递归例，但要想让过程既正确又是递归的，两者至少各有一个。

我们的 factorial 过程中有一个基例和一个递归例。你能找出它们吗？

检验理解

n 为 0 的情况是 factorial 的基例。考虑下面这个没有基例的 factorial 替代定义：

(define (factorial n)
  (* n (factorial (- n 1))))

这个替代定义有什么问题？

我们在过程内部调用 factorial 的第二种情况是递归例。注意，递归调用解决的是比原问题更小的问题（即 (factorial (- n 1))）。考虑下面这个 factorial 的替代定义：

(define (factorial n)
  (if (= n 0)
      1
      (factorial n)))

这个替代定义有什么问题？

你写的每个递归过程都必须满足下面哪些陈述？选择所有适用的项。

信念之跃

讲到这里，你可能仍然疑惑：一个函数怎么能用它自己来定义自己？如果你在定义 factorial 的过程中间使用 factorial，不是应该得到”factorial 尚未定义”的报错吗？要想让它工作，你得相信它能工作。从某种意义上说，这就是一次信念之跃（leap of faith）。

信念之跃实际上是编写递归过程的一种技巧。我们必须想象：你正在编写的过程，对于比当前着手解决的问题更小的任何问题，都已经能够正确工作。因此，当你思考如何计算 (factorial 5) 时，想象 (factorial 4) 已经解决了。这能让你自己的思路不至于陷入死循环。

回到第 0-2 课，我们指出过定义过程的一个重要性质：定义过程时，过程体不会被求值。这就是递归能够工作的技术原因。因此，define 是一个不求值其实参的特殊形式，它让过程体不被求值。过程体只有在你于定义之外调用该过程时才会被求值。

检验理解

这些表达式中哪些会在 Racket 中报错？选择所有适用的项。

把每个表达式输入 Racket 解释器，看看会发生什么。

再看 factorial

我们再来看看 factorial 的定义。

(define (factorial n)
  (if (= n 0)
      1
      (* n (factorial (- n 1)))))

如果我们想求值 (factorial 6)，就会进入 if 语句的 else 分支，把问题化归为 (* 6 (factorial 5))。为了进一步化简，我们需要求值 (factorial 5)。于是得到 (* 5 (factorial 4))。把它代入原表达式，得到 (* 6 (* 5 (factorial 4)))。再经过几次递归调用，我们会得到类似这样的东西：

(factorial 6)
(* 6 (factorial 5))
(* 6 (* 5 (factorial 4)))
(* 6 (* 5 (* 4 (factorial 3))))
(* 6 (* 5 (* 4 (* 3 (factorial 2)))))
(* 6 (* 5 (* 4 (* 3 (* 2 (factorial 1))))))
(* 6 (* 5 (* 4 (* 3 (* 2 (* 1 (factorial 0)))))))

(factorial 0) 该怎么办？这是基例，我们直接返回 1。于是得到这个表达式：

(* 6 (* 5 (* 4 (* 3 (* 2 (* 1 1))))))

这只是一串嵌套的乘法表达式，我们可以轻松地从内到外化简：

(* 6 (* 5 (* 4 (* 3 (* 2 1)))))
(* 6 (* 5 (* 4 (* 3 2))))
(* 6 (* 5 (* 4 6)))
(* 6 (* 5 24))
(* 6 120)
720

Racket 中有一个非常有用的过程叫 trace，它接收一个过程作为实参，在该过程被调用时展示过程的执行过程。

在 Racket 解释器中，定义 factorial 过程后输入 (trace factorial)，然后调用 (factorial 6)。你看到了什么？如果不想再跟踪这个过程，只需输入 (untrace factorial)。

例子：斐波那契数

考虑计算斐波那契数列，其中每个数都是前两个数之和：

$0, 1, 1, 2, 3, 5, 8, 13, 21$

一般地，斐波那契数可以由下面的规则定义：

$$Fib(n) = \begin{cases} 0, & \text{if } n = 0 \\ 1, & \text{if } n = 1 \\ Fib(n - 1) + Fib(n - 2), & \text{otherwise} \end{cases}$$

我们可以立刻把这个定义翻译成计算斐波那契数的递归过程：

(define (fib n)
  (cond ((= n 0) 0)
        ((= n 1) 1)
        (else (+ (fib (- n 1))
                 (fib (- n 2))))))

想想我们调用 (fib 2) 时会发生什么。这个过程会发起两次递归调用 (fib 1) 和 (fib 0)，分别返回 1 和 0。这两个数相加，过程返回 1。

你可能会想，真的有必要设两个独立的基例吗？想想看，如果我们去掉 n 为 1 时的基例会怎样。(fib 1) 会调用 (+ (fib 0) (fib -1))。(fib 0) 会返回 0，但 (fib -1) 永远到不了基例，过程会无限循环下去。

例子：猪拉丁

你可能熟悉猪拉丁（Pig Latin），这是一种语言游戏：把一个英文词的第一个辅音（或辅音簇）移到词的末尾，并在词尾加上 “ay”。例如，“pig” 变成 “igpay”，“trash” 变成 “ashtray”，“object” 变成 “objectay”。

我们可以用递归和辅助过程在 Racket 中实现猪拉丁：

(define (pigl wd)
  (if (pl-done? wd)
      (word wd 'ay)
      (pigl (word (bf wd) (first wd)))))

(define (pl-done? wd)
  (vowel? (first wd)))

(define (vowel? letter)
  (member? letter '(a e i o u)))

提醒一下，member? 是 Racket 的原始过程，接收两个实参——一个字母和一个词，若字母在词中则返回真。

猪拉丁在找到元音时即告完成，所以基例是 pl-done? 返回真的情况，这时只需在词尾拼接 “ay”。否则，在递归例中，它用词的 butfirst 与词的 first 拼接后的结果调用自身。想一想，如果词中不含元音会发生什么。

用你的 Racket 解释器试试这个 pigl 实现。别忘了利用 trace 过程！

例子：sum-sent

假设我们有一个数字句子，如下所示：

(define sent '(1 2 3 4 5))

我们想定义一个名为 sum-sent 的过程，求出 sent 中所有数之和，但我们也希望 sum-sent 能求任意数字句子的和。由于输出取决于输入句子的大小，我们必须使用递归！

让我们迈出信念之跃。想象 sum-sent 已经会计算去掉第一个数后的句子，例如 '(2 3 4 5)。为此，我们只需调用 (sum-sent (bf sent))，并且相信它会给出正确的和。既然如此，我们知道：

(sum-sent '(1 2 3 4 5)) ==> (+ 1 (sum-sent '(2 3 4 5)))

如果把它推广到任意数字句子，就得到了我们的递归例：

(+ (first sent) (sum-sent (bf sent)))

检验理解

如果我们就此打住，把 sum-sent 定义成这样，会发生什么？

(define (sum-sent sent)
  (+ (first sent) (sum-sent (bf sent))))

我们漏掉了基例！要解决这个问题，我们必须加一种情况来处理空句子。谓词 empty? 可以用来检查空句子。下面是 sum-sent 的完整版本：

(define (sum-sent sent)
  (if (empty? sent)
      0
      (+ (first sent) (sum-sent (bf sent)))))

检验理解

假设我们有一个负数句子 '(-1 -3 -4 -6)。Racket 会输出什么？先在纸上用上面的 sum-sent 代码推演一遍这个例子，不要输入解释器。然后，用解释器核对你的答案。

欢迎在 Racket 解释器中用 sum-sent 尝试更多例子。如果递归让你困惑，试着看看 trace 的输出。

练习

检验理解：count-ums

当你讲课的时候，如果说太多次 “um”，大家就会走神。写一个名为 count-ums 的过程，接收一个词句作为实参，统计这个句子中 “um” 出现的次数：

-> (count-ums '(today um we are going to um talk about the um combining method))
3

请用递归的方式写 count-ums。

提示 #1： 句子为空时应该怎样？

提示 #2： 句子的第一个词是 “um” 时应该怎样？

提示 #3： 句子的第一个词不是 “um” 时应该怎样？

检验理解：countdown

写一个名为 countdown 的过程，接收一个数，工作方式如下：

-> (countdown 10)
'(10 9 8 7 6 5 4 3 2 1 blastoff!)
-> (countdown 3)
'(3 2 1 blastoff!)
-> (countdown 1)
'(1 blastoff!)
-> (countdown 0)
'blastoff!