常见递归模式

「Every」模式（逐项变换）

下面是一个对数字句子中每个数求平方的过程：

(define (square-sent sent)
  (if (empty? sent)
      '()
      (se (square (first sent))
          (square-sent (bf sent)))))

下面是一个把句子中每个词都翻译成猪拉丁的过程：

(define (pigl-sent sent)
  (if (empty? sent)
      '()
      (se (pigl (first sent))
          (pigl-sent (bf sent)))))

这里的模式相当清晰。我们的递归例会对句子的 first 做一个直截了当的处理，比如求 square 或做 pigl，然后把这个结果与对句子的 butfirst 递归调用的结果组合起来。

检验理解

注意： 这是作业中的练习 5。

写一个名为 initials 的过程，接收一个句子作为实参，返回由句子中每个词的首字母组成的句子。例如：

-> (initials '(if i needed someone))
'(i i n s)

「Keep」模式（筛选保留）

在「Every」模式中，我们收集把词或句子中每个元素变换成别的东西后的结果。这一次我们来看一类不同的问题：选取部分元素，过滤掉其余元素。

首先，下面是一个从句子中筛选出三个字母的词的过程：

-> (define (keep-three-letter-words sent)
     (cond ((empty? sent) '())
           ((= (count (first sent)) 3)
             (se (first sent) (keep-three-letter-words (bf sent))))
           (else
             (keep-three-letter-words (bf sent)))))

-> (keep-three-letter-words '(one two three four five six seven))
'(one two six)

接着，下面是一个从词中筛选出元音字母的过程：

-> (define (keep-vowels wd)
     (cond ((empty? wd) "")
           ((vowel? (first wd))
             (word (first wd) (keep-vowels (bf wd))))
           (else
             (keep-vowels (bf wd)))))

-> (keep-vowels 'napoleon)
'aoeo

我们来看看「Every」模式和「Keep」模式的区别。首先，「Keep」类过程有三种情况，而不像大多数「Every」过程那样只有两种。在「Every」模式中，我们只需区分基例和递归例。而在「Keep」模式中，仍然有一个基例，但有两个递归例：我们必须决定是否把第一个可用的元素保留在返回值中。当我们保留一个元素时，保留的是元素本身，而不是元素的某个函数。

检验理解

写一个名为 numbers 的过程，接收一个句子作为实参，返回另一个只包含句子中数字的句子。你可能会觉得谓词 number? 有用。

-> (numbers '(76 trombones and 110 cornets))
'(76 110)

「Accumulate」模式（累加合并）

下面是两个遵循「Accumulate」模式的递归过程，这类模式把实参的所有元素合并成单一结果：

-> (define (addup nums)
     (if (empty? nums)
         0
         (+ (first nums)
            (addup (bf nums)))))
-> (addup '(8 3 6 1 10))
28

-> (define (scrunch-words sent)
     (if (empty? sent)
         "" ; 这是空词
         (word (first sent)
               (scrunch-words (bf sent)))))
-> (scrunch-words '(ack now ledge able))
'acknowledgeable

模式是什么？我们用某个合并器（+ 或 word）把当前处理的词与递归调用的结果连接起来。基例测试实参是否为空，但基例的返回值必须是合并器函数的单位元。

检验理解

在本小节中，我们讲解了各种函数作为递归的例子。下面哪些函数遵循累加合并模式？选择所有适用的项。

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

(define (count-ums sent)
  (cond ((empty? sent) 0)
        ((um? (first sent)) (+ 1 (count-ums (bf sent))))
        (else (count-ums (bf sent)))))

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