Wednesday, November 18, 2009

SICP Exercise 1.11

From SICP section 1.2.2 Tree Recursion

Exercise 1.11 gives us a function defined by the rules that

f(n) = n if n < 3
f(n) = f(n - 1) + 2f(n - 2) + 3f(n -3) if n ≥ 3

and asks us to write both recursive and iterative procedures for the function.

Since the function is defined recursively, it's any easy matter of a straight translation to Scheme to come up with the recursive definition.
(define (f n)
(if (< n 3)
(+ (f (- n 1))
(* 2 (f (- n 2)))
(* 3 (f (- n 3))))))

Here are the results of several sample runs:
> (f 0)
> (f 1)
> (f 2)
> (f 3)
> (f 4)
> (f 5)
> (f 6)
> (f 7)

The procedure above is a recursive process because the calculation of some of the state information is deferred until a later call of the procedure. Defining an iterative procedure means we have to remove this property. That means the iterative procedure has to keep track of all state information at each step of the calculation in explicit variables.

We can draw inspiration from the iterative definition of the Fibonacci procedure from the text.
(define (fib n)
(fib-iter 1 0 n))

(define (fib-iter a b count)
(if (= count 0)
(fib-iter (+ a b) a (- count 1))))

Here the fib procedure makes a call to the fib-iter procedure with initial values passed in for the first two parameters, along with a counter. We can use the same pattern for our iterative definition of f and f-iter.
(define (f n)
(if (< n 3)
(f-iter 2 1 0 n)))

(define (f-iter a b c count)
(if (< count 3)
(f-iter (+ a (* 2 b) (* 3 c))
(- count 1))))

In this definition of (f n), we start with the same check as before. If n is less than 3, then f(n) = n, so we need go no further. Otherwise, we iterate for as long as necessary.

f-iter takes three initial values a, b, and c, plus a counter. When counter reaches a value less than 3, then a will be equal to f(n), b will be equal to f(n-1), and c will be equal to f(n-2). Each time we iterate the value of a is recalculated and the old values of a and b are passed into the procedure for the parameters b and c. The counter is also decremented by 1.

You can copy and paste the code above into your Scheme interpreter to verify that we get the same results as the sample runs above.


For links to all of the SICP lecture notes and exercises that I've done so far, see The SICP Challenge.


Phil said...

The iterate function from my Standard Prelude makes this simple:

(define (iterate n f . bs)
  (let loop ((n n) (b (car bs)) (bs (cdr bs)) (xs '()))
    (if (zero? n) (reverse xs)
      (let ((new-bs (append bs (list (apply f b bs)))))
        (loop (- n 1) (car new-bs) (cdr new-bs) (cons b xs))))))

(define (f a b c)
  (+ (* 3 a) (* 2 b) c))

> (iterate 10 f 0 1 2)
  0 1 2 4 11 25 59 142 335 796)


Bill the Lizard said...

Excellent solution! I've read quite a bit further ahead than I've posted so far, but I haven't reached chapter 2 on Data Abastraction yet, so I couldn't have come up with that on my own. I'm sure to be checking back with your Standard Prelude often as I progress though the rest of the book. Thanks for posting.

Anonymous said...

I've been following your solutions as I go through the book myself. It's been very helpful. Thank you !

Greg said...

Hi Bill,

Thanks so much for posting your solutions - I've found them really helpful.

I was so close with 1.11, but without your help, I'd have probably given up. After staring at your solution for a while, I came up with a variant that you might like that avoids the double check against <3:

(define (fi n)
(fi-iter 2 1 0 n))

(define (fi-iter a b c count)
(if (= count 0)
(fi-iter (+ a
(* 2 b)
(* 3 c))
(- count 1))))

Kelly Kashuda said...

Hi, why is it that you initialize the parameters of the iterator function to 2, 1,0?

Bill the Lizard said...

Hi Kelly,

Those initial values are taken from calculating f(2), f(1), and f(0). Those values are needed to calculate the next value in the series, then that value is used to calculate the next one, and so on. It's similar to how the fib-iter function was seeded with the first two values in the sequence, just to get the ball rolling.

ilikezmusicz said...

Hi! still havent understood the iterative solution completely. Could you expand on how we would replicate for a different case. For example:
; f(n) = | n n <= 5
; | f(n - 1) + 3.f(n - 3) + 5.f(n - 5) if n > 5

Bill the Lizard said...


That problem is a little bit tricky (at least it was to me), because it looks like you only need to carry 3 values with each iteration (like the problem from the book), but if you step through a solution on paper you'll see that your program really needs to remember 5 values. Here's the solution I came up with.

(define (f2 n)
(if (<= n 5)
(f2-iter 5 4 3 2 1 n)))

(define (f2-iter a b c d e count)
(if (<= count 5)
(f2-iter (+ a (* 3 c) (* 5 e))
(- count 1))))

dhilipsiva திலிப்சிவ said...

Hey, bill. I am failing to understand something. Why check (< n 3) twice? Only once within the iter function should work just as fine right? I tried running it with n = 2,3,4 - and it gave correct results everytime. Am I failing to see an edge-case?

Bill the Lizard said...

dhilipsiva திலிப்சிவ,

Yes, you're right, that's not necessary. That came about from literally translating from the math function definition to code. I often try to do that for clarity, but it could be cleaned up to eliminate a needless extra comparison.

Abhirath Mahipal said...

Thanks a ton for all this work.

rizo1 said...

This post has helped clarify things for me, thank you so much!