Prompt
A function f is defined by the rule that f(n) = n if n < 3 and f(n)=f(n-1) + 2*f(n-2) + 3*f(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. Hint: for iteration, think about how you might code this using a for-loop in a language like Python.
Solution
The recursive form is easier to tackle – LISP’s probably do the best job of expressing recursive mathematical expressions due to the extremely minimal syntax.
(define (fn n)
(if (< n 3)
n
(+
(fn (- n 1))
(* 2 (fn (- n 2)))
(* 3 (fn ( - n 3)))
)
)
)Here’s an (incomplete) expansion using substitution of a call to (fn 10). Each newline denotes the expanded expression of the previous. Note the crazy combinatoric explosion of having not one but three recursive calls in the body – this creates a huge tree of deferred addition and multiplication operations.
(fn 10)
(+ (fn 9) (fn 8) (fn 7))
(+
(+ (fn 8) (fn 7) (fn 6))
(+ (fn 7) (fn 6) (fn 5))
(+ (fn 6) (fn 5) (fn 4)))
(+
(+
(+
(+ (fn 7) (fn 6) (fn 5))
(+ (fn 6) (fn 5) (fn 4))
(+ (fn 5) (fn 4) (fn 3))
)
(+
(+ (fn 6) (fn 5) (fn 4))
(+ (fn 5) (fn 4) (fn 3))
(+ (fn 4) (fn 3) (fn 2))
)
(+
(+ (fn 5) (fn 4) (fn 3))
(+ (fn 4) (fn 3) (fn 2))
(+ (fn 3) (fn 2) (fn 1))
)
)
(+
(+
(+ (fn 6) (fn 5) (fn 4))
(+ (fn 5) (fn 4) (fn 3))
(+ (fn 4) (fn 3) (fn 2))
)
(+
(+ (fn 5) (fn 4) (fn 3))
(+ (fn 4) (fn 3) (fn 2))
(+ (fn 3) (fn 2) (fn 1))
)
(+
(+ (fn 4) (fn 3) (fn 2))
(+ (fn 3) (fn 2) (fn 1))
(+ (fn 2) (fn 1) (fn 0))
)
)
(+
(+
(+ (fn 6) (fn 5) (fn 4))
(+ (fn 5) (fn 4) (fn 3))
(+ (fn 4) (fn 3) (fn 2))
)
(+
(+ (fn 5) (fn 4) (fn 3))
(+ (fn 4) (fn 3) (fn 2))
(+ (fn 3) (fn 2) (fn 1))
)
(+
(+ (fn 4) (fn 3) (fn 2))
(+ (fn 3) (fn 2) (fn 1))
(+ (fn 2) (fn 1) (fn 0))
)
)
)
...Eventually, this long recursive process bottoms out at the base case when we reach (fn 2), (fn 1), and (fn 0) since none of those invocations will reach the recursive section of the procedure. For example, (fn 2) will return 2 since 2 < 3. These values will play an important role in developing the iterative solution.
Iterative Form
There’s a few ways to think about this problem to get an intuition about what the iterative form might look like. One way is to consider a similar problem such as the fibonacci sequence.
Fibonacci Sequence
Consider a similar mathematical expression such as the fibonacci sequence expressed in scheme as a recursive procedure.
(define (fib n)
(if (< n 3)
1
(+ (fib (- n 1)) (fib (- n 2)))))It’s simpler since there aren’t additional multiplication operations and you’re only dealing with two recursive procedures in the body instead of 3, but it exhibits the same pattern of process growth (exponential expansion followed by contraction).
(fib 5)
(+ (fib 4) (fib 3))
(+ (+ (fib 3) (fib 2)) (fib 3))
(+ (+ (+ (fib 2) (fib 1)) (fib 2)) (fib 3))
...In the iterative form, you compute the next result using two values you currently have. You accumulate the answer from bottom up.
Here’s an example in scheme:
(define (fn n)
(define (iter x a b)
(if (> x n)
a
(iter (+ x 1) b (+ a b))))
(if (< n 2) 1 (iter 2 1 1)))a represents n - 2 and b represents n - 1. If we’re dealing with an n that’s less than 2, return 1. Otherwise kick off the recursive process with (iter 2 1 1). In each step, we compute the next result (+ a b) and feed that into our next recursive call as the new b.
There’s a few key insights from this iterative fibonacci definition:
- You start with two values and you use them to compute the next value. As the computation evolves, so do the two values you’re holding at any given point.
- Each step contains all the state you need to compute the next recursive step – there are no deferred operations
- Some notion of a “base case” is still necessary for knowing when to stop the accumulation. In this example we use
xand we stop whenxis greater than the initial argument to the fibonacci function.
Back to the problem
The fibonacci definition has a key trait in common with our problem. The current result based on n is based on computation using the last three results (instead of the two by fibonacci). In fact, they’re so similar that if you squint you might see the iterative form of our problem!
(define (fn n)
(define (iter x a b c)
(if (> x n)
c
(iter (+ x 1) b c (+ (* 3 a) (* 2 b) c))))
(if (< n 3) n (iter 3 0 1 2)))Unlike our fibonacci problem, we need to perform both addition and multiplication (+ (* 3 a) (* 2 b) c) in order to generate the next result. This is what moves the computation along. With fibonacci, there’s just an addition (+ a b) that gets computed as the new next value – but the same underlying pattern applies. Compute the next value, shift all three numbers forward and repeat.
Commentary
We got this problem on the first day of David Beazley’s SICP course and it completely destroyed my brain when I initially attempted to come up with the iterative solution to this.
The new syntax combined with the noise from all the additional computation in the recursive function made it very challenging. I didn’t really have an AHA moment to this until David shared his solution with us and I only realized the connection to fibonacci when I set out to write this post and revisit my understanding of the exercise.
I think this is a great problem in terms of noticing this tension between simplicity and beauty of recursive procedure definitions and their performance. You have this simple definition that grows wildly during runtime. Then you go forth and optimize it so that it doesn’t accumulate on the stack but get a far less intuitive looking definition as a result. There’s also the fun challenge of porting a recursive definition to an iterative one and noticing some of the difficulties in coming up with the right base cases. It’s really easy to make off by one errors with these problems and it’s not immediately obvious why the results are wrong until you go back to trace the mathematical definitions manually which can be tedious.