Exercise 4.21. Amazingly, Louis’s intuition in exercise 4.20 is correct. It is indeed possible to specify recursive procedures without using letrec (or even define), although the method for accomplishing this is much more subtle than Louis imagined. The following expression computes 10 factorial by applying a recursive factorial procedure:27
((lambda (n)
((lambda (fact)
(fact fact n))
(lambda (ft k)
(if (= k 1)
1
(* k (ft ft (- k 1)))))))
10)
a. Check (by evaluating the expression) that this really does compute factorials. Devise an analogous expression for computing Fibonacci numbers.
b. Consider the following procedure, which includes mutually recursive internal definitions:
(define (f x)
(define (even? n)
(if (= n 0)
true
(odd? (- n 1))))
(define (odd? n)
(if (= n 0)
false
(even? (- n 1))))
(even? x))
Fill in the missing expressions to complete an alternative definition of f, which uses neither internal definitions nor letrec:
(define (f x)
((lambda (even? odd?)
(even? even? odd? x))
(lambda (ev? od? n)
(if (= n 0) true (od? <??> <??> <??>)))
(lambda (ev? od? n)
(if (= n 0) false (ev? <??> <??> <??>)))))
一个只使用 lambda 写的递归 fibonacci 过程如下：
(define (fibonacci x)
((lambda (n)
((lambda (fibo)
(fibo fibo n))
(lambda (f k)
(cond ((= k 1) 1)
((= k 2) 1)
(else (+ (f f (- k 1))
(f f (- k 2))))))))
x))
只使用 lambda 来写递归过程的诀窍在于，需要将过程体本身在计算过程中传递，这样实现了“自己调用自己”。
使用 lambda 来重写过程 f，则为：
(define (f x)
((lambda (even? odd?)
(even? even? odd? x))
(lambda (ev? od? n)
(if (= n 0) true (od? ev? od? (- n 1))))
(lambda (ev? od? n)
(if (= n 0) false (ev? ev? od? (- n 1))))))
;;; tests begin
(load "../testframe.scm")
(assert= (fibonacci 1) 1)
(assert= (fibonacci 2) 1)
(assert= (fibonacci 3) 2)
(assert= (fibonacci 4) 3)
(assert= (fibonacci 5) 5)
(assert= (fibonacci 6) 8)
(asserteq? (f 10) true)
(asserteq? (f 11) false)