<< Previous exercise (4.20) | Index | Next exercise (4.22) >>

;; a ; this fib procedure uses the iterative version of fib. ((lambda (n) ((lambda (fib) (fib fib 1 0 n)) (lambda (fib a b count) (if (= count 0) b (fib fib (+ a b) a (- count 1)))))) 10)

As suspected from the recursive process minus recursive function, and confirmed through the footnote, this is a rather roundabout example of Haskell Curry's famous Y Combinator.

I couldn't figure out what they were getting at with the even/odd example, but here's a clearer version of what's going on in the factorial example:

;non-recursive factorial function (define fact-once (lambda (f) (lambda (n) (if (= n 0) 1 (* n (f (- n 1))))))) ;y-combinator (define Y (lambda (f) ((lambda (x) (x x)) (lambda (x) (f (lambda (y) ((x x) y))))))) (define factorial (Y fact-once)) (factorial 20) ;=2432902008176640000

@SophiaG, the odd? even? example is more sophisticated than a simple self-referential recursive function like fibonacci or factorial, since odd? and even? refer *to each other*, e.g. are *mutually* recursive. Hence, that example is neat because it shows that you can even create *mutually* recursive *sets* of functions without using define or letrec.

Btw the answer is this

```
(define (f x)
((lambda (even? odd?)
(even? even? odd? x)) ; note above
(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))))))
```

meteorgan