Matt Bowcock // mbowcock.com

As I said in a post earlier this week I’ve begun reading and working on the problems in SICP. I just read chapter 1 section 2.2 on tree recursion and completed problem 1.11 and plan to do 1.12 and 1.13. Problem 1.11 was creating recursive and iterative procedures to calculate the following function:

The recursive function was straight-forward:

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

Writing the procedure as an iterative process wasn’t as trivial. I initially expected it would be easy and sat down to write the code without really thinking about the problem, but wrapping my head around how to maintain the state needed for 3 function calls didn’t compute. So I resorted to pencil and paper – I wrote out the iterations of the function for n=0 through n=5 and the solution became clear:

(define (f-iter a b c count n)
  (cond ((< n 3) n)
    ((= count n) c)
      (else (f-iter b c (+ c (* 2 b) (* 3 a)) (+ count 1) n))))
     
(define (f2 n)
  (f-iter 0 1 2 2 n))

As a quick comparison of run-time for the 2 procedures I ran them with the same n value (n=30). For f(30) (recursive) the procedure took approximately 16 seconds to finish. For f2(30) (iterative) the procedure finished in less than a second. I tried higher numbers but the recursive process just takes to long – I killed the process at 3 minutes when running it for n=35. I’ve run the iterative process with n up to 150 and it completes in less than 1 second.