Excercise 1.11 Structure and Interpretation of Computer Programs (SICP)

I’m going through the “Structure and Interpretation of Computer Programs” as a way of compensating for my lack of geek cred. I was having some problem with wrapping my head around the iterative solution of this exercise (hey it was after a long day at work), so I cheated a bit and looked it up on the internet and found a solution here. So in order to come up with my own solution, I decided to implement a solution using the collector function or continuation technique for recursion shown or taught in the “Little Schemer” in chapter 8. Below is what I came up with

; Ex 1.11 ; recursive solution (define f-r (lambda (n) (cond ((< n 3) n) (else ( + (f-r (- n 1)) (* 2 (f-r (- n 2))) (* 3 (f-r (- n 3))))))))

; Iterative Solution (define f&co (lambda (n col) (cond ((< n 3) (col n 1 0)) ( else (f&co (- n 1) (lambda (a b c) (col (+ a (* 2 b) (* 3 c)) a b)))))))

(define f-i (lambda (n) (f&co n (lambda (a b c) a)))) (display “Recursive Solution”) (newline) (map f-r ‘(0 1 2 3 4 5 6)) (display “Iterative Solution using collector function”) (newline) (map f-i ‘(0 1 2 3 4 5 6))

Advertisements

Like this:

LikeLoading...

Related

This entry was posted on Saturday, January 16th, 2010 at 3:42 pm and is filed under Programming, Scheme. You can follow any responses to this entry through the RSS 2.0 feed.
You can leave a response, or trackback from your own site.

One Response to Excercise 1.11 Structure and Interpretation of Computer Programs (SICP)

Similar to fib…

(define (f2 n)

(define (iter-f count x x-1 x-2)

(if (= count n)

x

(iter-f (++ count)

(+ x (* 2 x-1) (* 3 x-2))

x

x-1)))

(if (< n 3)

n

(iter-f 2 2 1 0)))