SICP 1.2 exercises cont. 1Posted: January 5, 2013
I only managed to do one problem today. The important thing is consistence though so I’m not too ashamed.
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.