第六章，递归

一个过程体中可以包含对其它过程的调用，特别的是也可以调用自己。

  1. (define factorial
  2.  (lambda (n)
  3.     (if (= n 0) 1
  4.         (* n (factorial (- n 1))))))

这个递归过程用来计算一个数的阶乘。如果这个数是0，则结果为1。对于任何其它的值n，这个过程会调用其自身来完成n-1阶乘的计算，然后将这个子结果乘上n并返回最终产生的结果。

互递归过程也是可以的。下面判断奇偶数的过程相互进行了调用。

  1. (define is-even?
  2.  (lambda (n)
  3.     (if (= n 0) #t
  4.         (is-odd? (- n 1)))))
  6. (define is-odd?
  7.  (lambda (n)
  8.     (if (= n 0) #f
  9.         (is-even? (- n 1)))))

这里提供的两个过程的定义仅作为简单的互递归示例。Scheme已经提供了简单的判断过程even?和odd?。

6.1 letrec

如果希望将上面的过程定义为局部的，我们会尝试使用let结构：

  1. (let ((local-even? (lambda (n)
  2.                      (if (= n 0) #t
  3.                          (local-odd? (- n 1)))))
  4.       (local-odd? (lambda (n)
  5.                     (if (= n 0) #f
  6.                         (local-even? (- n 1))))))
  7.  (list (local-even? 23) (local-odd? 23)))

但这并不能成功，因为在初始化值过程中出现的local-even? 和 local-odd?指向的并不是这两个过程本身。

把let换成let*同样也不能奏效，因为这时虽然local-odd?中出现的local-even?指向的是前面刚创建好的局部的过程，但local-even? 中的local-odd?还是指向了别处。

为解决这个问题，Scheme提供了letrec结构。

  1. (letrec ((local-even? (lambda (n)
  2.                         (if (= n 0) #t
  3.                             (local-odd? (- n 1)))))
  4.          (local-odd? (lambda (n)
  5.                        (if (= n 0) #f
  6.                            (local-even? (- n 1))))))
  7.  (list (local-even? 23) (local-odd? 23)))

用letrec创建的词法变量不仅可以在letrec执行体中可见而且在初始化中也可见。letrec是专门为局部的递归和互递归过程而设置的。(这里也可以使用define来创建两个子结构的方式来实现局部递归)

6.2 命名let

使用letrec定义递归过程可以实现循环。如果我们想显示10到1的降数列，可以这样写：

  1. (letrec ((countdown (lambda (i)
  2.                       (if (= i 0) 'liftoff
  3.                           (begin
  4.                             (display i)
  5.                             (newline)
  6.                             (countdown (- i 1)))))))
  7.  (countdown 10))

这会在控制台上输出10到1，并会返回结果liftoff。

Scheme允许使用一种叫“命名let”的let变体来更简洁的写出这样的循环:

  1. (let countdown ((i 10))
  2.  (if (= i 0) 'liftoff
  3.       (begin
  4.         (display i)
  5.         (newline)
  6.         (countdown (- i 1)))))

注意在let的后面立即声明了一个变量用来表示这个循环。这个程序和先前用letrec写的程序是等价的。你可以将“命名let”看成一个对letrec结构进行扩展的宏。

6.3 迭代

上面定义的countdown函数事实上是一个递归的过程。Scheme只有通过递归才能定义循环，不存在特殊的循环或迭代结构。

尽管如此，上述定义的循环是一个“真”循环，与其他语言实现它们的循环的方法完全相同。也就是说,Scheme十分注意确保上面使用过的递归类型不会产生过程调用/返回开销。

Scheme通过一种消除尾部调用（tail-call elimination）的过程完成这个功能。如果你注意观察countdown的步骤，你会注意到当递归调用出现在countdown主体内时，就变成了“尾部调用”，或者说是最后完成的事情——countdown的每次调用要么不调用它自身，要么当它调用自身时把这个动作留在最后。对于一个Scheme语言的实现来说（解释器），这会使递归不同于迭代。因此，尽管用递归去写循环吧，这是安全的。

这是又一个有用的尾递归程序的例子：

  1. (define list-position
  2.   (lambda (o l)
  3.     (let loop ((i 0) (l l))
  4.       (if (null? l) #f
  5.           (if (eqv? (car l) o) i
  6.               (loop (+ i 1) (cdr l)))))))

list-position发现了o对象在列表l中第一次出现的索引。如果在列表中没有发现对象，过程将会返回#f。

这又是一个尾部递归过程，它将自身的参数列表就地反转，也就是使现有的列表内容产生变异，而没有分配一个新的列表：

  1. (define reverse!
  2.   (lambda (s)
  3.     (let loop ((s s) (r '()))
  4.       (if (null? s) r
  5.       (let ((d (cdr s)))
  6.             (set-cdr! s r)
  7.         (loop d s))))))

reverse!是一个十分有用的过程，它在很多Scheme方言中都能使用，例如MzScheme和Guile）

更多地递归例子（包括迭代）参见附录C。

6.4 用自定义过程映射整个列表

有一种特殊类型的迭代，对列表中每个元素，它都会重复相同的动作。Scheme为这种情况提供了两种程序：map和for-each。

map程序为给定列表中的每个元素提供了一种既定程序，并返回一个结果的列表。例如：

  1. (map add2 '(1 2 3))
  2. =>  (3 4 5)

for-each程序也为列表中的每个元素提供了一个程序，但返回值为空。这个程序纯粹是产生的副作用。例如：

  1. (for-each display
  2.   (list "one " "two " "buckle my shoe"))

这个程序在控制台上有显示字符串（在它们出现的顺序上）的副作用。

这个由map和for-each用在列表上的程序并不一定是单参数程序。举例来说，假设一个n参数的程序，map会接受n个列表，每个列表都是由一个参数所组成的集合，而map会从每个列表中取相应元素提供给程序。例如：

  1. (map cons '(1 2 3) '(10 20 30))
  2. =>  ((1 . 10) (2 . 20) (3 . 30))
  4. (map + '(1 2 3) '(10 20 30))
  5. =>  (11 22 33)