2.8 简单的递归

我们已经知道怎么写顺序及分支结构的程序，而且也知道怎么把代码定义为一个函数进行多次调用。如果我们想重复执行某些表达式要怎么做？我们可以用递归来实现。递归是一个简单的观念：在一个函数内部调用函数自己。初次接触的人可以会对递归产生迷惑，但是一旦掌握了递归，它将提供远超普通循环结构的强大表达能力。

一个递归函数就是在函数内部自己调用自己。下面的goodbye函数也许是最简单的递归函数了。

(define goodbye
  (lambda ()
    (goodbye)))

(goodbye) =>

这个函数没有返回值，而且不会结束。

很明显，要使递归函数有用，我们必须有某种办法来让它终止，大多数递归函数至少有两个基本元素：基本情况，以及递归步进。基本情况是递归结束的条件, giving the value of the procedure for some base argument. The recursion step gives the value in terms of the value of the procedure applied to a different argument. 为了使递归正常终止, 变化的参数必须以某种方式收敛到基本情况.

我们来思考怎么通过递归来求一个列表的长度。我们需要一个基本情况及递归步骤。在列表上递归的结束条件几乎都是列表为空。

(define length
  (lambda (ls)
    (if (null? ls)
        0
        (+ (length (cdr ls)) 1))))

(length '()) => 0
(length '(a)) => 1
(length '(a b)) => 2

if表达式询问列表是否为空列表，如果是，则值为0，这是基本情况；如果不是，则长度就是列表的cdr部分加上1. 这就是递归步进。

很多 Scheme 实现允许你跟踪一个函数的执行函数，看看它是怎么操作的。在 ChezScheme 里，一种跟踪函数的方式是输入(trace name)，其中，name 是定义在 top-level 中的函数。如果你跟踪上面所定义的length函数，并且传递给它一个参数'(a b c d)，你将会看到像下面的东西：

|(length (a b c d))
| (length (b c d))
| |(length (c d))
| | (length (d))
| | |(length ())
| | |0
| | 1
| |2
| 3
|4

缩进显示了递归的嵌套级别；在视觉上，坚线将函数应用与它们的返回值联系在一起。注意，每一次对length的调用，参数变得越来越小，最后变成空列表，空列表返回0,而外层的每一次调用都给内层的返回值加上1,最后得到结果为4。

我们来写一个list-copy函数，它的参数必须是一个列表，而且返回这个列表的拷贝。新列表里包含原列表中的所有元素。当需通过set-car!或者set-cdr!修改初始列表或者拷贝的时候，拷贝列表是有用的。我们后面会讲到。

(list-copy '()) => ()
(list-copy '(a b c)) => (a b c)

试试看在学习下面的内容之前你能不能把 list-copy 给定义出来

(define list-copy
  (lambda (ls)
    (if (null? ls)
        '()
        (cons (car ls)
              (list-copy (cdr ls))))))

list-copy的定义与length比较相似，它们结束的条件是相同的(null? ls)，在list-copy里，基本情况的值是()而不是0，因为我们在制造一个列表，而不是一个数字。递归调用的函数也是一样的，只不过把 +1 改成了 cons。list-copy每一次都把当前列表的car给cons到递归调用的返回值里去。

没有什么理由限制只能有一个递归出口（基本情况）。下面的 memv 函数检测列表 ls 中是否含有元素 x，如果含有，则返回以第一个 x 开头的子列表，如果没有，则返回 #f. memv 的返回值可作为列表被使用，也可以作为布尔值被用于条件表达式中。在 Scheme 里，所有不是 #f 的对象都被视为“真”，所括空列表。空列表与表示假的布尔值#f是不同的对象，这与 Common Lisp 是不同的。

(define memv
  (lambda (x ls)
    (cond
     ((null? ls) #f)
     ((eqv? (car ls) x) ls)
     (else (memv x (cdr ls))))))

(memv 'a '(a b b d)) => (a b b d)
(memv 'b '(a b b d)) => (b b d)
(memv 'c '(a b b d)) => #f
(memv 'd '(a b b d)) => (d)
(if (memv 'b '(a b b d))
    "yes"
    "no") => "yes"

这里有两个条件检测，所以使用了 cond 表达式。第一个 cond 子句检测 ls 是否为空列表，如果是，则返回 #f。第二个子句检测 ls 的 car 是否与 x 相等，如果相等则返回 ls 本身。

也有可能有一个以上的递归。和 memv 类似，函数 remv 从某个列表中删除所有指定的元素（remv 并非修改列表本身，而是生成了一个新的列表作为返回值）

(define remv
  (lambda (x ls)
    (cond
     ((null? ls) '())
     ((eqv? (car ls) x) (remv x (cdr ls)))
     (else (cons (car ls) (remv x (cdr ls)))))))

(remv 'a '(a b b d)) => (b b d)
(remv 'b '(a b b d)) => (a d)
(remv 'c '(a b b d)) => (a b b d)
(remv 'd '(a b b d)) => (a b b)

到现在为止，递归还只能在列表的 cdr 上进行。然面，有时候需要在列表的 car 及 cdr 上同时进行递归。下面的tree-copy 函数将 pair (列表本质上是一种特殊的 pair）视作树，而不是普通的列表。car为左子树，cdr为右子树. 函数访问树的每一个节点，并且生成一个相同的拷贝。

(define tree-copy
  (lambda (tr)
    (if (not (pair? tr))
        tr
        (cons (tree-copy (car tr))
              (tree-copy (cdr tr))))))

(tree-copy '((a . b) . c)) => ((a . b) . c)

这种情况叫做双重递归。

至此，那些对别的编程语言有经验的读者也许会怀疑，在 Scheme 中是否需要类似于 while 或者 for 之类专门的迭代（循环）结构。这是没有必要的，在 Scheme 里，迭代可以通过递归清晰而简洁地表达出来。递归更通用，并且消除了对变量赋值的依赖，使得代码更可靠。一些递归本质上就是迭代（尾递归，Scheme 会执行尾递归优化，消除调用栈的开销），3.2 节会对此展开更多的讨论。通常情况下没必要对此做区分，而应当将集中精力在写出简洁，正确的程序上来。

在离开递归的讨论之前，我们来思考一种以重复为目的的特殊形式——映射。下面的函数 abs-all 接受一个数字列表，并且返回一个列表包含原里列里所有元素的绝对值。

(define abs-all
  (lambda (ls)
    (if (null? ls)
        '()
        (cons (abs (car ls))
              (abs-all (cdr ls))))))

(abs-all '(1 -2 3 -4 5 -6)) => (1 2 3 4 5 6)

这个函数通过在传入的列表中的每一个元素上应用函数 abs 而得到另一个新的列表，我们称之为：abs-all 将 abs 函数映射到输入列表上，产生一个新列表。将一个函数映射到一个列表上是一件很普遍的事，所以 Scheme 提供了 map 函数，它将第一个参数（一个函数）映射到它的第二个参数（一个列表）上。我们可以这样定义 abs-all 函数。

(define abs-all
  (lambda (ls)
    (map abs ls)))

我们甚至不需要定义一个 abs-all 函数，因为直接使用 map 函数更为简短和清晰

(map abs '(1 -2 3 -4 5 -6)) => (1 2 3 4 5 6)

当然，我们也可以用 lambda 创建一个匿名函数作为 map 的参数

(map (lambda (x) (* x x))
     '(1 -3 -5 7)) => (1 9 25 49)

我们还可以将接受多个参数的函数映射到多个列表上

(map cons '(a b c) '(1 2 3)) => ((a . 1) (b . 2) (c . 3))

列表的长度必须相同，而且列表的数量要与映射函数的参数数量相同。

重新查看最上面定义的 abs-all 函数，下面是一个受限的，递归版本的 map1 函数，它可以将一个函数映射到一个单独的列表上。

(define map1
  (lambda (p ls)
    (if (null? ls)
        '()
        (cons (p (car ls))
              (map1 p (cdr ls))))))

(map1 abs '(1 -2 3 -4 5 -6)) => (1 2 3 4 5 6)

它与 abs-all 的不同仅仅是将对 abs 函数的调用改成了对新的参数 p 的调用。更通用的 map 函数的定义会在 5.4 节给出。

练习 2.8.1

描述一下，如果你改变了tree-copy函数中，cons 的参数顺序，会发生什么。

练习 2.8.2

请查阅 6.3 节的 append 函数，然后自己写一个版本的append函数，如果在你定义的 append 函数里交换了 append 的参数顺序，会发生什么？

练习 2.8.3

定义一个函数make-list，它接受一个正整数 n 以及一个对象，返回一个新列表，长度为 n，每一个元素都是由第二个参数传入的对象。

(make-list 7 '()) => (() () () () () () ())

[提示：基本的测试条件可以是(= n 0)，递归步进可以是(- n 1)]

练习 2.8.4

过程 list-ref及list-tail分别返回一个列表的 “第n个元素” 以及 “倒数第n个cdr”

(list-ref '(1 2 3 4) 0) => 1
(list-tail '(1 2 3 4) 0) => (1 2 3 4)
(list-ref '(a short (nested) list) 2) => (nested)
(list-tail '(a short (nested) list) 2) => ((nested) list)

请定义出这两个函数。

练习 2.8.5

在练习 2.7.2 中，在定义 shorter 的时候，你使用了 length函数，它返回两个列表中较短的一个，或者两个相同长度的列表中的第一个。现在重新定义 shorter 函数，不要使用 length

[提示：定义一个递归的辅助函数 shorter?，并且用它替换长度比较]

练习 2.8.6

现在，你看到的所有递归函数都是直接递归，意思是说，每一个函数在自己的函数体内使用一个新的参数来调用自己。其实可以写出两个互相递归调用的函数来，叫做间接递归。请定义两个函数odd?及even?，让它们互相调用。

[提示：当参数为0的时候，这两个函数分别要怎么对待？]

练习 2.8.7

使用 map 定义一个函数 transpose，它接受一个列表作为参数，列表中每个元素都是点对，返回如下的新列表

(transpose '((a . 1) (b . 2) (c . 3))) => ((a b c) 1 2 3)

[提示：((a b c) 1 2 3) 等价于 ((a b c) . (1 2 3))]