# sicp-ex-4.21

meteorgan

```

;; a
(lambda (n)
((lambda (fib)
(fib fib n))
(lambda (f n)
(cond ((= n 0) 0)
((= n 1) 1)
(else (+ (f f (- n 2)) (f f (- n 1))))))))

;; b. filling the box as sequence:
ev? od? (- n 1)
ev? od? (- n 1)
```

Rptx

```

;; 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)
```

SophiaG

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

```