Scheme Exercise (Structure and Interpretation book)

RevertTS · 2006-09-19 23:03:32

I've been working through the Structure and Interpretation of Computer Programs book and have hit a bit of a problem. Since I chose to use this book as part of my curriculum, my teacher doesn't actually know much of anything about Lisp or its varients, so I was hoping to get a bit of help.

The problem is:

Section 1.2 wrote:

Exercise 1.11. A function f is defined by the rule that f(n) = n if n<3> 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.

I have no trouble writing a recursive procedure/recursive process, but I am having trouble writing it iteratively; I'm not familiar enough with Lisp to know how to model this, and I don't know how to do it iteratively with three branching sections. I'm assuming it'd require some sort of running total and a number of variables to save the state, and I was thinking about possibly trying to work from the bottom up, but I'm not real sure.

If anyone can help me with an iterative version, it'd be much appreciated; right now I'm just confused.

allucid · 2006-09-19 23:30:59

Use tail recursion. If you have not covered that yet, let me know (or check wikipedia's entries on iteration and tail recurision).

RevertTS · 2006-09-20 02:05:16

I've read over some stuff on tail-recursion, but I'm still struggling with this.
I think I made a bit of progress, though.

JulesJacobs · 2006-09-20 18:15:32

Let's write down some examples of this function:

f(0) = 0
f(1) = 1
f(2) = 2
f(3) = f(2) + 2*f(1) + 3*f(0)
f(4) = f(3) + 2*f(2) + 3*f(1)
f(5) = f(4) + 2*f(3) + 3*f(2)

If you compute the value of f(5) recursively you do it like this:

f(5) = f(4) + 2*f(3) + 3*f(2)
f(4) = f(3) + 2*f(2) + 3*f(1)
f(3) = f(2) + 2*f(1) + 3*f(0)
f(2) = 2
f(1) = 1
f(0) = 0
f(3) = 2 + 2*1 + 3*0
...

If you do this iteratively you do it the other way around:

f(0) = 0
f(1) = 1
f(2) = 2
f(3) = f(2) + 2*f(1) + 3*f(0)
f(4) = f(3) + 2*f(2) + 3*f(1)
f(5) = f(4) + 2*f(3) + 3*f(2)

The last three lines have the same structure:

f(n) = previous + 2*before-previous + 3*before-before-previous

If you want to compute f(n) you only need the 3 previous values at any time. To compute f(3) you need f(2), f(1) and f(0). Let's give these short names:

previous = a
before-previous = b
before-before-previous = c

If you want to compute f(3):

a = f(2) = 2
b = f(1) = 1
c = f(0) = 0

Now we compute f(4):

a = f(3) = ?
b = f(2) = 2
c = f(1) = 1

For b and c it's easy to define them in terms of previous values a, b and c:

b = previous-a
c = previous-b

Verify that this is correct.

a is a little tickier because we need the original formula:

a = previous-a + 2*previous-b + 3*previous-c

So this is what we have now:

a = previous-a + 2*previous-b + 3*previous-c
b = previous-a
c = previous-b

Let's rewrite that with arrow notation:

a -> a + 2*b + 3*c
b -> a
c -> b

These arrows mean that you compute them in parallel; the a in b -> a is still the previous a, and not the new a generated by a -> a + 2*b + c.

Computing f(5) with this iterative method:

a -> 2
b -> 1
c -> 0

These are the base-case values because f(n) = n if n <3> 2 + 2*1 + 3*0 = 4
b -> 2
c -> 1

(n = 4)

a -> 4 + 2*2 + 3*1 = 11
b -> 4
c -> 2

(n = 5)

a -> 11 + 2*4 + 3*2 = 25
b -> 11
c -> 4

The answer of f(5) is in a: 25.

The basic structure of the procedure looks like this:

(define (f n)
  (define (iter counter a b c)
    (if (= counter n)
      c
      (iter (+ counter 1)
             ; new a
             ; new b
             ; new c
             )))
  (iter 0 2 1 0))

The rest is an exercise.

Don't shoot me if this isn't correct! (I didn't implement the actual procedure ;-))

dadexter · 2006-09-20 18:51:24

Ok, I've gone cross-eyed again :shock:

JulesJacobs · 2006-09-20 19:16:13

What does that mean? (english is not my native language)

Is my explanation too complicated?

Here is the full code:

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

(define (fi n) ; f-iterative
  (define (iter counter a b c)
    (if (= counter n)
     c
     (iter (+ counter 1)
           (+ a (* 2 b) (* 3 c))
           a
           b)))
  (iter 0 2 1 0))

RevertTS · 2006-09-20 20:47:23

Thank you so much!

Walking through it like that really helped; now I just have to explain it to my teacher.

SleepyDog · 2006-09-21 00:33:18

I'm also struggling through SICP (on my own, we're doing java in my CS class ). Thanks a lot that post, it really helped.

RevertTS · 2006-09-21 02:24:16

I had to use Java for my first two years of CS, but this year I'm in independent study, so I chose to do Scheme and C.

Still have to use Java for competitions, though.

JulesJacobs · 2006-09-23 20:06:21

RevertTS wrote:

Still have to use Java for competition, though.

Scheme is cheating? ;-)

Arch Linux

#1 2006-09-19 23:03:32

Scheme Exercise (Structure and Interpretation book)

#2 2006-09-19 23:30:59

Re: Scheme Exercise (Structure and Interpretation book)

#3 2006-09-20 02:05:16

Re: Scheme Exercise (Structure and Interpretation book)

#4 2006-09-20 18:15:32

Re: Scheme Exercise (Structure and Interpretation book)

#5 2006-09-20 18:51:24

Re: Scheme Exercise (Structure and Interpretation book)

#6 2006-09-20 19:16:13

Re: Scheme Exercise (Structure and Interpretation book)

#7 2006-09-20 20:47:23

Re: Scheme Exercise (Structure and Interpretation book)

#8 2006-09-21 00:33:18

Re: Scheme Exercise (Structure and Interpretation book)

#9 2006-09-21 02:24:16

Re: Scheme Exercise (Structure and Interpretation book)

#10 2006-09-23 20:06:21

Re: Scheme Exercise (Structure and Interpretation book)

Board footer