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:

((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? <??> <??> <??>)))))

————————————————————————————————————————————————————————————————————————

a.

((lambda (n)
   ((lambda (f)
      (f f n))
    (lambda (fib k)
      (cond ((= k 0) 0)
            ((= k 1) 1)
            (else (+ (fib fib (- k 1))
                     (fib fib (- k 2))))))))
 10)

The idea is simple: construct a function (lambda (f) (f f n)) which 
calls its argument f with f as the first argument.  This gives the 
anonymous internal function a way to refer to itself, by using its first 
formal parameter fib as a reference to itself.

Another interesting way to look at this is: let the inner lambda be a 
function which, when provided with a function that calculates the 
Fibonnaci sequence for n greater than 1, and an argument n, calculates 
the nth Fibonnaci number.  Since this function then satisfies the 
requirements of the recursive call, the outer lambda can call this 
function with itself as the first argument and get a correct answer.

b.

(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))))))