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

xdavidliu

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