第七章 重復(fù)

7.1?簡介

本章中我會介紹重復(fù)。通過重復(fù)，你可以編寫“通常的”程序。雖然也可以使用do表達式，但Scheme中通常通過遞歸實現(xiàn)重復(fù)。

7.2?遞歸

在自己的定義中調(diào)用自己的函數(shù)叫做遞歸函數(shù)（Recursive Function）。雖然這聽起來很奇怪，但是循環(huán)的常見方法。If you have an analogy comparing functions to machines, recursion makes no sense. 然而，正因為函數(shù)式過程，函數(shù)調(diào)用自己是有意義的。比如說，讓我們來考察一下文獻調(diào)研吧。你可能需要去閱讀你正在閱讀的文獻所引用的文獻（cited-1）。進一步，你可能還需要去閱讀文件（cite-1）所引用的其它文獻。這樣，文獻調(diào)研就是一個遞歸的過程，你也可以重復(fù)這個調(diào)研過程直到滿足了特定條件（比如說，你累了）。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函數(shù)

(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)調(diào)用(fact 4)，(fact 4)調(diào)用(fact 3)，最后(fact 1)被調(diào)用。(fact 5)，(fact 4)……以及(fact 1)都被分配了不同的存儲空間，直到(fact (- i 1))返回一個值之前，(fact i)都會保留在內(nèi)存中，由于存在函數(shù)調(diào)用的開銷，這通常會占用更多地內(nèi)存空間和計算時間。

然而，遞歸函數(shù)可以以一種簡單的方式表達重復(fù)。表是被遞歸定義的，進而表和遞歸函數(shù)可以很好地配合。例如，一個讓表中所有元素翻倍的函數(shù)可以像下面這樣寫。如果參數(shù)是空表，那么函數(shù)應(yīng)該停止計算并返回一個空表。

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

練習(xí)1

用遞歸編寫下面的函數(shù)。

1. 用于統(tǒng)計表中元素個數(shù)的my-length函數(shù)。（length是一個預(yù)定義函數(shù)）。
2. 一個求和表中元素的函數(shù)。
3. 一個分別接受一個表ls和一個對象x的函數(shù)，該函數(shù)返回從ls中刪除x后得到的表。
4. 一個分別接受一個表ls和一個對象x的函數(shù)，該函數(shù)返回x在ls中首次出現(xiàn)的位置。索引從0開始。如果x不在ls中，函數(shù)返回#f。

7.3?尾遞歸

普通的遞歸調(diào)用并不高效因為它既浪費存儲空間又具有函數(shù)調(diào)用開銷。與之相反，尾遞歸函數(shù)包含了計算結(jié)果，當(dāng)計算結(jié)束時直接將其返回。特別地，由于Scheme規(guī)范要求尾遞歸調(diào)用轉(zhuǎn)化為循環(huán)，因此尾遞歸調(diào)用就不存在函數(shù)調(diào)用開銷。

[代碼片段2]展示了[代碼片段1]中函數(shù)fact的尾遞歸版本。

[代碼片段2] fact函數(shù)的尾遞歸版本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并不等待其它函數(shù)的計算結(jié)果，因此當(dāng)它計算結(jié)束時即從內(nèi)存中釋放。計算通過修改fact-rec的參數(shù)來演進，這基本上等同于循環(huán)。如上文所述，Scheme將尾遞歸轉(zhuǎn)化為循環(huán)，Scheme就無需提供循環(huán)的語法來實現(xiàn)重復(fù)。

練習(xí)2

用尾遞歸編寫下面的函數(shù)

1. 用于翻轉(zhuǎn)表元素順序的my-reverse函數(shù)。（reverse函數(shù)是預(yù)定義函數(shù)）
2. 求和由數(shù)構(gòu)成的表。
3. 將一個代表正整數(shù)的字符串轉(zhuǎn)化為對應(yīng)整數(shù)。例如，”1232”會被轉(zhuǎn)化為1232。不需要檢查不合法的輸入。提示，字符到整數(shù)的轉(zhuǎn)化是通過將字符#\0……#\9的ASCII減去48，可以使用函數(shù)char->integer來獲得字符的ASCII碼。函數(shù)string->list可以將字符串轉(zhuǎn)化為由字符構(gòu)成的表。

7.4?命名let

命名let（named let）可以用來表達循環(huán)。[代碼片段3]中的函數(shù)fact-let展示了如何使用命名let來計算階乘。fact-let函數(shù)使用了一個命名let表達式(loop)，這與在[代碼片段2]中展示的fact-rec函數(shù)是不同的。在被注釋為;1的那行，代碼將參數(shù)n1和p都初始化為n。再每次循環(huán)后，參數(shù)在被注釋為;2的那行更新：將n1減1，而將p乘以(n1 - 1)。

在Scheme中，用命名let來表達循環(huán)是俗成的方法。

[代碼片段3] fact-let的實現(xiàn)

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

練習(xí)3

用命名let編寫下面的函數(shù)。

1. 練習(xí)1的問題3和問題4；
2. 練習(xí)2中的函數(shù)；
3. range函數(shù)：返回一個從0到n的表（但不包含n）。

7.5?letrec

letrec類似于let，但它允許一個名字遞歸地調(diào)用它自己。語法letrec通常用于定義復(fù)雜的遞歸函數(shù)。[代碼片段4]展示了fact函數(shù)的letrec版本。

[代碼片段4] fact函數(shù)的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是定義局部變量的俗成方式。

練習(xí)4

用letrec重寫練習(xí)2。

7.6?do表達式

雖然并不常見，但語法do也可用于表達重復(fù)。它的格式如下：

(do binds (predicate value)
    body)

變量在binds部分被綁定，而如果predicate被求值為真，則函數(shù)從循環(huán)中逃逸（escape）出來，并返回值value，否則循環(huán)繼續(xù)進行。

binds部分的格式如下所示：

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

變量p1，p2，…被分別初始化為i1，i2，…并在循環(huán)后分別被更新為u1，u2，…。

[代碼片段5]演示了fact的do表達式版本。

[代碼片段5] fact函數(shù)的do表達式版本

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

變量n1和p分別被初始化為n和n，在每次循環(huán)后分別被減去1和乘以(n1 - 1)。當(dāng)n1變?yōu)?code>1時，函數(shù)返回p。

我認為do比命名let還要復(fù)雜一些。

練習(xí)5

用do表達式重寫練習(xí)2。

7.7?小結(jié)

現(xiàn)在你可以用我講解過的技巧來編寫常見程序了。通常來說，命名let用于編寫簡單的循環(huán)，而letrec則是用來寫復(fù)雜的局部遞歸函數(shù)。

下一章中我講講解高階函數(shù)。高階函數(shù)使得你的代碼更加“Scheme風(fēng)味”。

7.8?習(xí)題解答

7.8.1?練習(xí)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?練習(xí)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?練習(xí)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?練習(xí)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?練習(xí)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)))