SICP 1.2 exercises cont. 1

I only managed to do one problem today. The important thing is consistence though so I’m not too ashamed.

1.11

A function f is defined by the rule that f(n) = n if n < 3 and f(n) = f(n – 1) + 2f(n – 2) + 3f(n – 3) if n >= 3. Write a procedure that computes f by means of a recursive process. Write a procedure that computes f by means of an iterative process.

Recursive is easy…

(define (f n)
  (if (< n 3)
      n
    (+ (f (- n 1))
       (* 2 (f (- n 2)))
       (* 3 ( f (- n 3))))))

Iterative took some trial and error. I actually kept procrastinating on this problem because it always felt like I almost had it but never really did until half an hour before the day ended. This is how I envisioned blogging everyday would help me because I always feel like I need to have done something, no matter how little, to be better than I was yesterday.

(define (f2 n)
  (cond ((< n 3)
         n)
        (else
         (f-iter 0 (- n 2) 2 1 0))))

(define (f-iter count max-count current fn-1 fn-2)
  (cond ((= count max-count)
         current)
        (else
         (f-iter (+ count 1) max-count (+ current (* 2 fn-1) (* 3 fn-2)) current fn-1))))

Comment: Actually, I assume there are much better ways to answer this problem, but this seems to work. The hard part was realizing exactly which values needed to be remembered.

Advertisements


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s