第六章，遞歸
=====
一個過程體中可以包含對其它過程的調用，特別的是也可以調用自己。
```scheme
(define factorial
(lambda (n)
(if (= n 0) 1
(* n (factorial (- n 1))))))
```
這個遞歸過程用來計算一個數的階乘。如果這個數是0，則結果為1。對于任何其它的值n，這個過程會調用其自身來完成n-1階乘的計算，然后將這個子結果乘上n并返回最終產生的結果。
互遞歸過程也是可以的。下面判斷奇偶數的過程相互進行了調用。
```scheme
(define is-even?
(lambda (n)
(if (= n 0) #t
(is-odd? (- n 1)))))
(define is-odd?
(lambda (n)
(if (= n 0) #f
(is-even? (- n 1)))))
```
這里提供的兩個過程的定義僅作為簡單的互遞歸示例。Scheme已經提供了簡單的判斷過程`even?`和`odd?`。
## 6.1 letrec
如果希望將上面的過程定義為局部的，我們會嘗試使用let結構：
```scheme
(let ((local-even? (lambda (n)
(if (= n 0) #t
(local-odd? (- n 1)))))
(local-odd? (lambda (n)
(if (= n 0) #f
(local-even? (- n 1))))))
(list (local-even? 23) (local-odd? 23)))
```
但這并不能成功，因為在初始化值過程中出現的`local-even?` 和 `local-odd?`指向的并不是這兩個過程本身。
把`let`換成`let*`同樣也不能奏效，因為這時雖然`local-odd?`中出現的`local-even?`指向的是前面剛創建好的局部的過程，但`local-even?` 中的`local-odd?`還是指向了別處。
為解決這個問題，Scheme提供了`letrec`結構。
```scheme
(letrec ((local-even? (lambda (n)
(if (= n 0) #t
(local-odd? (- n 1)))))
(local-odd? (lambda (n)
(if (= n 0) #f
(local-even? (- n 1))))))
(list (local-even? 23) (local-odd? 23)))
```
用`letrec`創建的詞法變量不僅可以在`letrec`執行體中可見而且在初始化中也可見。`letrec`是專門為局部的遞歸和互遞歸過程而設置的。(這里也可以使用`define`來創建兩個子結構的方式來實現局部遞歸)
## 6.2 命名let
使用`letrec`定義遞歸過程可以實現循環。如果我們想顯示10到1的降數列，可以這樣寫：
```scheme
(letrec ((countdown (lambda (i)
(if (= i 0) 'liftoff
(begin
(display i)
(newline)
(countdown (- i 1)))))))
(countdown 10))
```
這會在控制臺上輸出10到1，并會返回結果`liftoff`。
Scheme允許使用一種叫“命名let”的`let`變體來更簡潔的寫出這樣的循環:
```scheme
(let countdown ((i 10))
(if (= i 0) 'liftoff
(begin
(display i)
(newline)
(countdown (- i 1)))))
```
注意在`let`的后面立即聲明了一個變量用來表示這個循環。這個程序和先前用`letrec`寫的程序是等價的。你可以將“命名let”看成一個對`letrec`結構進行擴展的宏。
## 6.3 迭代
上面定義的`countdown`函數事實上是一個遞歸的過程。Scheme只有通過遞歸才能定義循環，不存在特殊的循環或迭代結構。
盡管如此，上述定義的循環是一個“真”循環，與其他語言實現它們的循環的方法完全相同。也就是說,Scheme十分注意確保上面使用過的遞歸類型不會產生過程調用/返回開銷。
Scheme通過一種消除尾部調用（tail-call elimination）的過程完成這個功能。如果你注意觀察`countdown`的步驟，你會注意到當遞歸調用出現在`countdown`主體內時，就變成了“尾部調用”，或者說是最后完成的事情——`countdown`的每次調用要么不調用它自身，要么當它調用自身時把這個動作留在最后。對于一個Scheme語言的實現來說（解釋器），這會使遞歸不同于迭代。因此，盡管用遞歸去寫循環吧，這是安全的。
這是又一個有用的尾遞歸程序的例子：
```scheme
(define list-position
(lambda (o l)
(let loop ((i 0) (l l))
(if (null? l) #f
(if (eqv? (car l) o) i
(loop (+ i 1) (cdr l)))))))
```
`list-position`發現了`o`對象在列表`l`中第一次出現的索引。如果在列表中沒有發現對象，過程將會返回`#f`。
這又是一個尾部遞歸過程，它將自身的參數列表就地反轉，也就是使現有的列表內容產生變異，而沒有分配一個新的列表：
```scheme
(define reverse!
(lambda (s)
(let loop ((s s) (r '()))
(if (null? s) r
(let ((d (cdr s)))
(set-cdr! s r)
(loop d s))))))
```
`reverse!`是一個十分有用的過程，它在很多Scheme方言中都能使用，例如MzScheme和Guile）
更多地遞歸例子（包括迭代）參見附錄C。
## 6.4 用自定義過程映射整個列表
有一種特殊類型的迭代，對列表中每個元素，它都會重復相同的動作。Scheme為這種情況提供了兩種程序：`map`和`for-each`。
`map`程序為給定列表中的每個元素提供了一種既定程序，并返回一個結果的列表。例如：
```scheme
(map add2 '(1 2 3))
=> (3 4 5)
```
`for-each`程序也為列表中的每個元素提供了一個程序，但返回值為空。這個程序純粹是產生的副作用。例如：
```scheme
(for-each display
(list "one " "two " "buckle my shoe"))
```
這個程序在控制臺上有顯示字符串（在它們出現的順序上）的副作用。
這個由`map`和`for-each`用在列表上的程序并不一定是單參數程序。舉例來說，假設一個n參數的程序，`map`會接受n個列表，每個列表都是由一個參數所組成的集合，而`map`會從每個列表中取相應元素提供給程序。例如：
```scheme
(map cons '(1 2 3) '(10 20 30))
=> ((1 . 10) (2 . 20) (3 . 30))
(map + '(1 2 3) '(10 20 30))
=> (11 22 33)
```
