Mark Needham

Thoughts on Software Development

SICP: Iterative process vs Recursive process functions

with 2 comments

I was working my way through some of the exercises in SICP over the weekend and one that I found particularly interesting was 1.11 where you have to write a function by means of a recursive process and then by means of an iterative process.

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.

To write that function recursively is relatively straight forward:

(in Clojure)

(defn f [n]
  (if (< n 3)
    n
    (+ (f (- n 1)) (* 2 (f (- n 2))) (* 3 (f (- n 3))))))

The solution to this problem by means of an iterative process will still use recursion but we won’t need to keep a track of all the previous calls to the function on the stack because we will keep the current state of the calculation in parameters that we pass to the function.

This will also mean that the second function is tail recursive.

I was initially a bit stuck about how to write this function but luckily Shishir was around and had a better idea.

The solution we eventually ended up with looks like this:

(defn g [n a b c count]
  (cond (< n 3) n
	(> count (- n 3)) a
	:else (g n (+ a (* 2 b) (* 3 c)) a b (+ count 1))))
 
(defn f [n]
  (g n 2 1 0 0))

I think there should be a way to get rid of the first condition but I’m not sure exactly how to do that – the solution on the wiki is a bit better.

The difference in the approach to writing the iterative version is that we needed to think about solving the problem from the bottom down rather than from the top down.

In this case that meant that we needed to pass around parameters for the first 3 values of n i.e. 1, 2 and 3 which had values of 0, 1 and 2 respectively.

The way we’ve passed the parameters through the function means that ‘a’ represents the value that we’ll eventually want to return when we reach the exit condition of the function.

We pass ‘a’ and ‘b’ into the next function call as ‘b’ and ‘c’ which means that we lose the current f(n-3) value on the next recursion of the function.

I still find writing these types of functions quite tricky so I’d be interested in any advice that people have about this.

Be Sociable, Share!

Written by Mark Needham

September 16th, 2010 at 6:48 pm

Posted in SICP

Tagged with

  • I’ve been meaning to go through the whole SICP book for a while now. I even joined a group some people from the brazilian python comunity formed online to study it, but unfornately everyone’s schedules got in the way and it didn’t go forward.

    I’m not any good into writing good tail recursive functions either but I would strongly recomend watching the video classes. I’ve saw the first five or six and they are full of great insights, even though they are from 1986!

    You can watch them here, if you’re interested: http://www.youtube.com/user/MIT#grid/user/E18841CABEA24090

  • FWIW my initial solution came out like this: https://gist.github.com/753674

    Like you, I find it helps to think about the iterative processes as bottom up rather than top down.

    In my head, I (somewhat fuzzily) map the parameters to object state as appropriate. SICP has given me an interesting perspective on this. For comparison, see the over-complicated Ruby Fib implementation (class IncrementalFibSequenceGenerator) I did before I’d started the book – there’s no need to keep all the historical state: https://github.com/ashleymoran/xpman_even_fib/blob/ashleymoran-seb-201011112025/lib/euler_fib.rb

    Have you / are you planning to continue working through SICP? It’s one of my side-projects for the new year, and I’m on the lookout for others doing the same. Let me know if you ever get back into it 🙂