重复

本章中我会介绍重复。通过重复，你可以编写“通常的”程序。虽然也可以使用do表达式，但Scheme中通常通过递归实现重复。

递归

在自己的定义中调用自己的函数叫做递归函数（Recursive Function）。虽然这听起来很奇怪，但是循环的常见方法。

然而，正因为函数式过程，函数调用自己是有意义的。比如说，让我们来考察一下文献调研吧。

你可能需要去阅读你正在阅读的文献所引用的文献（cited-1）。进一步，你可能还需要去阅读文件（cite-1）所引用的其它文献。这样，文献调研就是一个递归的过程，你也可以重复这个调研过程直到满足了特定条件（比如说，你累了）。

我们通常使用计算阶乘来解释递归。

(define (fact n)
  (if (= n 1)
      1
      (* n (fact (- n 1)))))

(fact 5)的计算过程如下：

(fact 5)
⇒ 5 * (fact 4)
⇒ 5 * 4 * (fact 3)
⇒ 5 * 4 * 3 * (fact 2)
⇒ 5 * 4 * 3 * 2 * (fact 1)
⇒ 5 * 4 * 3 * 2 * 1
⇒ 5 * 4 * 3 * 2
⇒ 5 * 4 * 6
⇒ 5 * 24
⇒ 120

(fact 5)调用(fact 4)，(fact 4)调用(fact 3)，最后(fact 1)被调用。(fact 5)，(fact 4)……以及(fact 1)都被分配了不同的存储空间，直到(fact (- i 1))返回一个值之前，(fact i)都会保留在内存中，由于存在函数调用的开销，这通常会占用更多地内存空间和计算时间。

然而，递归函数可以以一种简单的方式表达重复。表是被递归定义的，进而表和递归函数可以很好地配合。

例如，一个让表中所有元素翻倍的函数可以像下面这样写。如果参数是空表，那么函数应该停止计算并返回一个空表。

(define (list*2 ls)
  (if (null? ls)
      '()
      (cons (* 2 (car ls))
             (list*2 (cdr ls)))))

练习 1

尾递归

普通的递归调用并不高效因为它既浪费存储空间又具有函数调用开销。与之相反，尾递归函数包含了计算结果，当计算结束时直接将其返回。特别地，由于Scheme规范要求尾递归调用转化为循环，因此尾递归调用就不存在函数调用开销。

(define (fact-tail n)
  (fact-rec n n))

(define (fact-rec n p)
  (if (= n 1)
      p
      (let ((m (- n 1)))
    (fact-rec m (* p m)))))

fact-tail计算阶乘的过程像这样：

(fact-tail 5)
⇒ (fact-rec 5 5)
⇒ (fact-rec 4 20)
⇒ (fact-rec 3 60)
⇒ (fact-rec 2 120)
⇒ (fact-rec 1 120)
⇒ 120

因为fact-rec并不等待其它函数的计算结果，因此当它计算结束时即从内存中释放。计算通过修改fact-rec的参数来演进，这基本上等同于循环。如上文所述，Scheme将尾递归转化为循环，Scheme就无需提供循环的语法来实现重复。

练习 2

用尾递归编写下面的函数

提示，字符到整数的转化是通过将字符#\0……#\9的ASCII减去48，可以使用函数char->integer来获得字符的ASCII码。

函数string->list可以将字符串转化为由字符构成的表。

命名let

命名let（named let）可以用来表达循环。[代码片段3]中的函数fact-let展示了如何使用命名let来计算阶乘。

fact-let函数使用了一个命名let表达式(loop)，这与在[代码片段2]中展示的fact-rec函数是不同的。在被注释为;1的那行，代码将参数n1和p都初始化为n。

再每次循环后，参数在被注释为;2的那行更新：将n1减1，而将p乘以(n1 - 1)。

在Scheme中，用命名let来表达循环是俗成的方法。

(define (fact-let n)
  (let loop((n1 n) (p n))           ; 1
    (if (= n1 1)                    
    p
    (let ((m (- n1 1)))
      (loop m (* p m))))))      ; 2

练习 3

用命名let编写下面的函数。

letrec

letrec类似于let，但它允许一个名字递归地调用它自己。语法letrec通常用于定义复杂的递归函数。[代码片段4]展示了fact函数的letrec版本。

(define (fact-letrec n)
  (letrec ((iter (lambda (n1 p)
           (if (= n1 1)
               p
               (let ((m (- n1 1)))
             (iter m (* p m)))))))     ; *
    (iter n n)))

正如被注释为;*的那行代码所示，局部变量iter可以在它的定义里面引用它自己。语法letrec是定义局部变量的俗成方式。

练习 4

用letrec重写练习2。

do表达式

虽然并不常见，但语法do也可用于表达重复。它的格式如下：

(do binds (predicate value)
    body)

变量在binds部分被绑定，而如果predicate被求值为真，则函数从循环中逃逸（escape）出来，并返回值value，否则循环继续进行。

binds部分的格式如下所示：

[binds] → ((p1 i1 u1) (p2 i2 u2) ... )

变量p1，p2，…被分别初始化为i1，i2，…并在循环后分别被更新为u1，u2，…。

(define (fact-do n)
  (do ((n1 n (- n1 1)) (p n (* p (- n1 1)))) ((= n1 1) p)))

变量n1和p分别被初始化为n和n，在每次循环后分别被减去1和乘以(n1 - 1)。当n1变为1时，函数返回p。

我认为do比命名let还要复杂一些。

练习 5

用do表达式重写 练习2。