3.2 更多的递归

在2.8节中，我们已经看到了如何使用 define 定义一个递归函数。在那之前，我还看到了使用let将一个函数绑定到一个局部变量上。很自然，我们可能想知道，用let绑定的局部函数是否可以递归调用？答案是否定的，至少是不直观的方法。如果你尝试求值下面的表达式

(let ([sum (lambda (ls)
             (if (null? ls)
                 0
                 (+ (car ls) (sum (cdr ls)))))])
  (sum '(1 2 3 4 5)))

很可能会遇到一个提示告诉你sum未定义。这是因为变量sum仅仅在let表达式的 body 中可见，而 lambda表达式并不是 body 的一部分，我们可以把 sum 作为参数传递给它自己，来绕过这个限制。

(let ([sum (lambda (sum ls)
             (if (null? ls)
                 0
                 (+ (car ls) (sum sum (cdr ls)))))])
  (sum sum '(1 2 3 4 5))) => 15

这是个聪明的做法，但是有一个更简单的办法，那就是letrec。和let类似，letrec包含了一些'变量-值'对，其 body 由一系列表达式构成

(letrec ((var expr) ...) body1 body2 ...)

但是和 let不同的是，var ...等变量并不仅仅在 body 中可见，它在所有的 expr ... 表达式中也是可见的，这样，我们就重写上面的表达式：

(letrec ([sum (lambda (ls)
                (if (null? ls)
                    0
                    (+ (car ls) (sum (cdr ls)))))])
  (sum '(1 2 3 4 5))) => 15

我们可以使用letrec定义出互相递归调用的函数来，比如函数 even?以及odd?，这是练习 2.8.6 的主题。

(letrec ([even?
          (lambda (x)
            (or (= x 0)
                (odd? (- x 1))))]
         [odd?
          (lambda (x)
            (and (not (= x 0))
                 (even? (- x 1))))])
  (list (even? 20) (odd? 20))) => (#t #f)

在letrec表达式里，expr ...系列子表达式通常是 lambda表达式，虽然并不总是这样。该表达式必须遵守的一个限制是，对每一个 expr的求值不能依赖任何变量 var ... 的求值。如果expr都是lambda表达式的话，总是可以满足这个限制，因为尽管某个 var变量在 lambda表达式中被引用，但是直到lambda表达式生成的函数在letrec的 body 中被调用，被引用的 var才需要被求值。下面的 letrec表达式满足此限制。

(letrec ([f (lambda () (+ x 2))]
         [x 1])
  (f)) => 3

但是下面的并不满足

(letrec ([y (+ x 2)]
         [x 1])
  y)

在这种情况下，会抛出一个异常，提示x未定义。

我们可以通过 letrec 来隐藏功能单一的助手函数，这样就不必要将它们都定义为顶级（全局）函数，从而避免混淆全局命名空间。这一点可以由下面的list?函数来证明, which follows the "hare and tortoise" algorithm outlined in 练习 2.9.8.

(define list?
  (lambda (x)
    (letrec ([race
              (lambda (h t)
                (if (pair? h)
                    (let ([h (cdr h)])
                      (if (pair? h)
                          (and (not (eq? h t))
                               (race (cdr h) (cdr t)))
                          (null? h)))
                    (null? h)))])
      (race x x))))

如上例所示，当递归函数仅仅在函数外部的一个地方被调用时，使用另一种称为"命名的let"来写往往更加清晰。Named let 表达式的形式如下：

(let name ((var expr) ...)
  body1 body2 ...)

命名的 let 和未命名的 let 类似，它将每一个变量 var ... 绑定到每一个值expr ...，每一个变量的作用域是 let 表达式的 body，每一个 var 仅仅在 body 内部可见，在其它的 expr ...里是不可见的。此外，变量name在 body 内部被绑定为一个可以递归调用的函数，该函数的参数就是每一个 var ...的新值。

下面是用 Named let 重写的 list? 函数

(define list?
  (lambda (x)
    (let race ([h x] [t x])
      (if (pair? h)
          (let ([h (cdr h)])
            (if (pair? h)
                (and (not (eq? h t))
                     (race (cdr h) (cdr t)))
                (null? h)))
          (null? h)))))

就像普通的let表达式可以表示为将lambda表达式直接应用到参数上一样，Named let 表达式也可以表示为对参数的递归过程的应用。一个 Named let 的形式

(let name ((var expr) ...)
  body1 body2 ...)

可以用letrec重写为

((letrec ((name (lambda (var ...) body1 body2 ...)))
   name)
 expr ...)

或者重写为

(letrec ((name (lambda (var ...) body1 body2 ...)))
  (name expr ...))

provided that the variable name does not appear free within expr ....

正如我们在2.8节中讨论的那样，一些递归本质上是迭代，并且像迭代那样执行。一当个函数调用发生在一个lambda表达式的尾部位置（见下文）时，它被认为是一个尾调用，Scheme 实现必须 妥善 地将尾调用处理成 "goto" 或者跳转。当一个函数在尾部调用自己，或者通过一系列尾调用间接地调用了自己时，即所谓的”尾递归“。因为尾调用被优化为跳转，所以尾递归可以用于无限迭代，而不用担心栈溢出。从而可以代替由其它编程语言提供的限制性更强的循环结构。

如果在一个lambda表达式内部调用了另外一个函数，该函数的返回值作为 lambda表达式的返回值直接返回，即调用之后没有额外的运算，这就是所谓的尾部调用。例如，a call is in tail position if it is the last expression in the body of a lambda expression, the consequent or alternative part of an if expression in tail position, the last subexpression of an and or or expression in tail position, the last expression in the body of a let or letrec in tail position, etc. 下面的表达式中，对函数 f 的每一次调用都是尾调用，但是对函数 g 的调用不是尾调用。

(lambda () (f (g)))
(lambda () (if (g) (f) (f)))
(lambda () (let ([x 4]) (f)))
(lambda () (or (g) (f)))

在上面的表达式中，对 f 的调用总是直接返回，而对 g 的调用并不是直接返回。

普通递归以及 Named let, 特别是 Named let，提供了一种实现许多算法的自然的方式，不论是迭代的，递归的，还是部分迭代部分递归的算法；程序员不用负担两种不同的机制。

下面的两个factorial定义使用 Named let 表达式计算非负整数 n 的阶乘。第一个使用了阶乘的递归定义： n! = n x (n-1)! , 0 的阶乘是 1.

(define factorial
  (lambda (n)
    (let fact ([i n])
      (if (= i 0)
          1
          (* i (fact (- i 1)))))))

(factorial 0) => 1
(factorial 1) => 1
(factorial 2) => 2
(factorial 3) => 6
(factorial 10) => 3628800

第二个是迭代版本，使用了阶乘的迭代定义： n! = n x (n-1) x (n-2) x ... x 1 , 其中使用了一个累加器 a 来保存中间值。

(define factorial
  (lambda (n)
    (let fact ([i n] [a 1])
      (if (= i 0)
          a
          (fact (- i 1) (* a i))))))

一个类似的问题是计算给定的第 n 个斐波那契数。斐波那契数列是一个无限的整数序列，0, 1, 1, 2, 3, 5, 8, 等等。其中的每个数字都是前面两个数字的和。

计算第 n 个斐波那契数的程序，最自然的是下面的递归定义

(define fibonacci
  (lambda (n)
    (let fib ([i n])
      (cond
        [(= i 0) 0]
        [(= i 1) 1]
        [else (+ (fib (- i 1)) (fib (- i 2)))]))))

(fibonacci 0) => 0
(fibonacci 1) => 1
(fibonacci 2) => 1
(fibonacci 3) => 2
(fibonacci 4) => 3
(fibonacci 5) => 5
(fibonacci 6) => 8
(fibonacci 20) => 6765
(fibonacci 30) => 832040

该方法的每一个步骤都需要先计算出前面两个斐波那契数，因此是 双重递归 。例如，在计算 (fibonacci 4)，需要先计算出 (fib 3) 以及 (fib 2), 计算 (fib 3) 需要先计算出 (fib 2) 和 (fib 1)， 并且，计算 (fib 2) 又需要先计算出 (fib 1) 和 (fib 0). 这是非常低效的，随着 n 的增长，它变的更加低效。更有效的解决办法是引入两个和上面的阶乘函数类似的累加器，a1 表示当前斐波那契数， a2 表示上一个。

(define fibonacci
  (lambda (n)
    (if (= n 0)
        0
        (let fib ([i n] [a1 1] [a2 0])
          (if (= i 1)
              a1
              (fib (- i 1) (+ a1 a2) a1))))))

0 在此被视为一种特殊情况，因为它前面没有有效的值了。这样就允许我们使用单独的基本情况 (= i 1)。使用这个迭代算法计算第 n 个斐波那契数所需要的时间随着 n 线性增长，与双重递归的版本相比，这是一个显著的差异。为了获得直观的体会，请尝试使用两个版本的函数分别计算 (fibonacci 35) 以及 (fibonacci 40)，看看它们分别需要多少时间。

我们还可以通过给予某个比较小的输入参数，通过跟踪递归的执行来体会它们之前的差异。下面的第一个跟踪显示了非线性递归版本的 fibonacci 函数中的 fib 的调用，输入值为 5

|(fib 5)
| (fib 4)
| |(fib 3)
| | (fib 2)
| | |(fib 1)
| | |1
| | |(fib 0)
| | |0
| | 1
| | (fib 1)
| | 1
| |2
| |(fib 2)
| | (fib 1)
| | 1
| | (fib 0)
| | 0
| |1
| 3
| (fib 3)
| |(fib 2)
| | (fib 1)
| | 1
| | (fib 0)
| | 0
| |1
| |(fib 1)
| |1
| 2
|5

注意，其中对 2, 1, 和 0 分别多次重复调用了 fib。

下面的过程跟踪显示了在尾递归版本中对 fib 的调用，输入仍然为 5

|(fib 5 1 0)
|(fib 4 1 1)
|(fib 3 2 1)
|(fib 2 3 2)
|(fib 1 5 3)
|5

显然，区别大了去了。

到目前为止所展示的 Named let 例子不是尾递归的就是非尾递归的。经常会发生在同一个表达式内部，一个递归调用是尾递归，而另外一个递归调用却不是尾递归的情况。下面的factor函数计算某个非负整数的质因子，在函数factor中，对f的第一次调用不是尾递归，而第二次调用则是尾递归。

(define factor
  (lambda (n)
    (let f ([n n] [i 2])
      (cond
        [(>= i n) (list n)]
        [(integer? (/ n i))
         (cons i (f (/ n i) i))]
        [else (f n (+ i 1))]))))

(factor 0) => (0)
(factor 1) => (1)
(factor 12) => (2 2 3)
(factor 3628800) => (2 2 2 2 2 2 2 2 3 3 3 3 5 5 7)
(factor 9239) => (9239)

在 Chez Scheme 里，可以把 let 替换成 trace-let，来跟踪函数 f 的调用过程，当求值(factor 120)时，函数f的调用过程如下图所示，它展示了尾递归和非尾递归之间的差异。

|(f 120 2)
| (f 60 2)
| |(f 30 2)
| | (f 15 2)
| | (f 15 3)
| | |(f 5 3)
| | |(f 5 4)
| | |(f 5 5)
| | |(5)
| | (3 5)
| |(2 3 5)
| (2 2 3 5)
|(2 2 2 3 5)

对f的非尾调用相对于其调用者增加一级缩进，其为其调用者依然保持活动，而尾调用都处在相同的缩进级别上。

练习 3.2.1 在3.2节中定义的递归函数中，哪些是尾递归，哪些不是？

练习 3.2.2 重写factor函数，使用letrec来取代 named let，你更喜欢哪一个版本？

练习 3.2.3 下面的letrec表达式可以用 named let 重写吗？如果不能，请回答为什么不能；如果你认为可以，那就把它写出来。

(letrec ([even?
          (lambda (x)
            (or (= x 0)
                (odd? (- x 1))))]
         [odd?
          (lambda (x)
            (and (not (= x 0))
                 (even? (- x 1))))])
  (even? 20))

练习 3.2.4 Rewrite both definitions of fibonacci given in this section to count the number of recursive calls to fib, using a counter similar to the one used in the cons-count example of Section 2.9. Count the number of recursive calls made in each case for several input values. What do you notice?

练习 3.2.5 Augment the definition of let given in Section 3.1 to handle named let as well as unnamed let, using two rules.

练习 3.2.6 The following definition of or is simpler than the one given in Section 3.1.

(define-syntax or ; incorrect!
  (syntax-rules ()
    [(_) #f]
    [(_ e1 e2 ...)
     (let ([t e1])
       (if t t (or e2 ...)))]))

Say why it is not correct. [Hint: Think about what would happen if this version of or were used in the even? and odd? example given on page 66 for very large inputs.]

练习 3.2.7 The definition of factor is not the most efficient possible. First, no factors of n besides n itself can possibly be found beyond . Second, the division (/ n i) is performed twice when a factor is found. Third, after 2, no even factors can possibly be found. Recode factor to correct all three problems. Which is the most important problem to solve? Are there any additional improvements you can make?