相互遞迴
相互遞迴就是多個函式互相定義,最常見的就是兩個函式,比如f和g,f的定義中用到g,而g的定義中用到f。
相互遞迴一樣有無限遞迴的可能,最簡單的:
f:x->g(x)
g:x->f(x)
給個最簡單的沒有無限遞迴的例子,判斷一個正整數是不是偶數或者是不是奇數,用C++來描述如下:
bool is_odd(unsigned x); bool is_even(unsigned x) { if(x == 0u) return true; return is_odd(x-1u); } bool is_odd(unsigned x) { if(x == 0u) return false; return is_even(x-1u); }
以上效率雖然不高(甚至不優化的情況下,可能會崩棧),但是is_even和is_odd兩個函式畢竟是相互定義的,也是相互遞迴的一個經典例子。
Scheme當然一樣支援相互遞迴,r5rs中也是以上述奇偶來做例子。
(define (even? x) (if (zero? x) #t (odd? (- x 1)) ) ) (define (odd? x) (if (zero? x) #f (even? (- x 1)) ) )
再給個稍微複雜的例子,Scheme裡的append是個常用的函式,它可以傳入一組列表,得到這組列表首尾拼接在一起的列表。比如:(append '(1 2 3) '(4 5 6) '(7 8 9))得到(1 2 3 4 5 6 7 8 9)。
每個人學習Scheme的過程,基本必然伴隨著append函式的自我實現。
以下是其中一種實現(當然,append有好幾種不同的實現思想):
(define (append . lst) (if (null? lst) '() ((apply _append (cdr lst)) (car lst)) ) ) (define (_append . lst) (cond ((null? lst) (lambda (x) x)) ((null? (cdr lst)) (lambda (x) (if (null? x) (car lst) (cons (car x) ((_append (car lst)) (cdr x))) ) ) ) (else (_append (apply append lst))) ) )
當然,_append一般應該實現在append的內部,我這麼寫也是為了表示的清楚一點。這種寫法是一種相對高階一點的寫法,採用的運算元方式,不斷用閉包來傳遞資訊,並使用了相互遞迴,append和_append兩個函式互相定義。
當然,一開始就說了,相互遞迴完全可以不只是兩個函式之間的關係,可以是多個函式之間的關係。
我這裡給個例子,把正整數按照除以3得到的餘數分為三類,把整除3的數稱為type0,把除以3餘1的數稱為type1,把除以3餘2的數稱為type2。於是定義三個謂詞函式type0? type1? type2?
以下為實現:
(define (type0? x) (if (= x 0) #t (type2? (- x 1)) ) ) (define (type1? x) (if (= x 0) #f (type0? (- x 1)) ) ) (define (type2? x) (if (= x 0) #f (type1? (- x 1)) ) )
我們可以看到,
type0?的定義中用到type2?
type1?的定義中用到type0?
type2?的定義中用到type1?
測試一下,
(for-each (lambda (x) (display x)(newline)) (map (lambda (x) (cons x (map (lambda (f) (f x)) (list type0? type1? type2?)) ) ) (range 20) ) )
得到
(0 #t #f #f)
(1 #f #t #f)
(2 #f #f #t)
(3 #t #f #f)
(4 #f #t #f)
(5 #f #f #t)
(6 #t #f #f)
(7 #f #t #f)
(8 #f #f #t)
(9 #t #f #f)
(10 #f #t #f)
(11 #f #f #t)
(12 #t #f #f)
(13 #f #t #f)
(14 #f #f #t)
(15 #t #f #f)
(16 #f #t #f)
(17 #f #f #t)
(18 #t #f #f)
(19 #f #t #f)