[TOC=2]
## 7.1?簡介
本章中我會介紹重復。通過重復，你可以編寫“通常的”程序。雖然也可以使用`do`表達式，但Scheme中通常通過遞歸實現重復。
## 7.2?遞歸
在自己的定義中調用自己的函數叫做**遞歸函數（Recursive Function）**。雖然這聽起來很奇怪，但是循環的常見方法。If you have an analogy comparing functions to machines, recursion makes no sense. 然而，正因為函數式過程，函數調用自己是有意義的。比如說，讓我們來考察一下文獻調研吧。你可能需要去閱讀你正在閱讀的文獻所引用的文獻（cited-1）。進一步，你可能還需要去閱讀文件（cite-1）所引用的其它文獻。這樣，文獻調研就是一個遞歸的過程，你也可以重復這個調研過程直到滿足了特定條件（比如說，你累了）。Thus, an analogy that compares functions in programming languages to some kind of human activities (say, literature survey) is useful to understand recursive functions.
我們通常使用計算階乘來解釋遞歸。
[代碼片段1] 用于計算階乘的fact函數
~~~
(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
>
> 用遞歸編寫下面的函數。
>
> 1. 用于統計表中元素個數的`my-length`函數。（`length`是一個預定義函數）。
> 2. 一個求和表中元素的函數。
> 3. 一個分別接受一個表`ls`和一個對象`x`的函數，該函數返回從`ls`中刪除`x`后得到的表。
> 4. 一個分別接受一個表`ls`和一個對象`x`的函數，該函數返回`x`在`ls`中首次出現的位置。索引從`0`開始。如果`x`不在`ls`中，函數返回`#f`。
## 7.3?尾遞歸
普通的遞歸調用并不高效因為它既浪費存儲空間又具有函數調用開銷。與之相反，尾遞歸函數包含了計算結果，當計算結束時直接將其返回。特別地，由于Scheme規范要求尾遞歸調用轉化為循環，因此尾遞歸調用就不存在函數調用開銷。
[代碼片段2]展示了[代碼片段1]中函數`fact`的尾遞歸版本。
[代碼片段2] fact函數的尾遞歸版本fact-tail
~~~
(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
>
> 用尾遞歸編寫下面的函數
>
> 1. 用于翻轉表元素順序的`my-reverse`函數。（`reverse`函數是預定義函數）
> 2. 求和由數構成的表。
> 3. 將一個代表正整數的字符串轉化為對應整數。例如，”1232”會被轉化為1232。不需要檢查不合法的輸入。提示，字符到整數的轉化是通過將字符#\0……#\9的ASCII減去48，可以使用函數`char->integer`來獲得字符的ASCII碼。函數`string->list`可以將字符串轉化為由字符構成的表。
## 7.4?命名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`來表達循環是俗成的方法。
[代碼片段3] fact-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`編寫下面的函數。
>
> 1. 練習1的問題3和問題4；
> 2. 練習2中的函數；
> 3. `range`函數：返回一個從`0`到`n`的表（但不包含`n`）。
## 7.5?letrec
`letrec`類似于`let`，但它允許一個名字遞歸地調用它自己。語法`letrec`通常用于定義復雜的遞歸函數。[代碼片段4]展示了`fact`函數的`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。
## 7.6?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`，…。
[代碼片段5]演示了`fact`的`do`表達式版本。
[代碼片段5] fact函數的do表達式版本
~~~
(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。
## 7.7?小結
現在你可以用我講解過的技巧來編寫常見程序了。通常來說，命名`let`用于編寫簡單的循環，而`letrec`則是用來寫復雜的局部遞歸函數。
下一章中我講講解高階函數。高階函數使得你的代碼更加“Scheme風味”。
## 7.8?習題解答
### 7.8.1?練習1
~~~
; 1
(define (my-length ls)
(if (null? ls)
0
(+ 1 (my-length (cdr ls)))))
; 2
(define (my-sum ls)
(if (null? ls)
0
(+ (car ls) (my-sum (cdr ls)))))
; 3
(define (remove x ls)
(if (null? ls)
'()
(let ((h (car ls)))
((if (eqv? x h)
(lambda (y) y)
(lambda (y) (cons h y)))
(remove x (cdr ls))))))
; 4
(define (position x ls)
(position-aux x ls 0))
(define (position-aux x ls i)
(cond
((null? ls) #f)
((eqv? x (car ls)) i)
(else (position-aux x (cdr ls) (1+ i)))))
~~~
### 7.8.2?練習2
~~~
; 1
(define (my-reverse ls)
(my-reverse-rec ls ()))
(define (my-reverse-rec ls0 ls1)
(if (null? ls0)
ls1
(my-reverse-rec (cdr ls0) (cons (car ls0) ls1))))
;-------------------
; 2
(define (my-sum-tail ls)
(my-sum-rec ls 0))
(define (my-sum-rec ls n)
(if (null? ls)
n
(my-sum-rec (cdr ls) (+ n (car ls)))))
;--------------------
; 3
(define (my-string->integer str)
(char2int (string->list str) 0))
(define (char2int ls n)
(if (null? ls)
n
(char2int (cdr ls)
(+ (- (char->integer (car ls)) 48)
(* n 10))))
~~~
### 7.8.3?練習3
~~~
; 1
(define (remove x ls)
(let loop((ls0 ls) (ls1 ()))
(if (null? ls0)
(reverse ls1)
(loop
(cdr ls0)
(if (eqv? x (car ls0))
ls1
(cons (car ls0) ls1))))))
; 2
(define (position x ls)
(let loop((ls0 ls) (i 0))
(cond
((null? ls0) #f)
((eqv? x (car ls0)) i)
(else (loop (cdr ls0) (1+ i))))))
; 3
(define (my-reverse-let ls)
(let loop((ls0 ls) (ls1 ()))
(if (null? ls0)
ls1
(loop (cdr ls0) (cons (car ls0) ls1)))))
; 4
(define (my-sum-let ls)
(let loop((ls0 ls) (n 0))
(if (null? ls0)
n
(loop (cdr ls0) (+ (car ls0) n)))))
; 5
(define (my-string->integer-let str)
(let loop((ls0 (string->list str)) (n 0))
(if (null? ls0)
n
(loop (cdr ls0)
(+ (- (char->integer (car ls0)) 48)
(* n 10))))))
; 6
(define (range n)
(let loop((i 0) (ls1 ()))
(if (= i n)
(reverse ls1)
(loop (1+ i) (cons i ls1)))))
~~~
### 7.8.4?練習4
~~~
; 1
(define (my-reverse-letrec ls)
(letrec ((iter (lambda (ls0 ls1)
(if (null? ls0)
ls1
(iter (cdr ls0) (cons (car ls0) ls1))))))
(iter ls ())))
; 2
(define (my-sum-letrec ls)
(letrec ((iter (lambda (ls0 n)
(if (null? ls0)
n
(iter (cdr ls0) (+ (car ls0) n))))))
(iter ls 0)))
; 3
(define (my-string->integer-letrec str)
(letrec ((iter (lambda (ls0 n)
(if (null? ls0)
n
(iter (cdr ls0)
(+ (- (char->integer (car ls0)) 48)
(* n 10)))))))
(iter (string->list str) 0)))
~~~
### 7.8.5?練習5
~~~
; 1
(define (my-reverse-do ls)
(do ((ls0 ls (cdr ls0)) (ls1 () (cons (car ls0) ls1)))
((null? ls0) ls1)))
; 2
(define (my-sum-do ls)
(do ((ls0 ls (cdr ls0)) (n 0 (+ n (car ls0))))
((null? ls0) n)))
; 3
(define (my-string->integer-do str)
(do ((ls0 (string->list str) (cdr ls0))
(n 0 (+ (- (char->integer (car ls0)) 48)
(* n 10))))
((null? ls0) n)))
~~~
