This is the first in what I hope will be many posts talking about Structure and Interpretation of Computer Programs, by Abelson and Sussman. This and future posts on this subject will be based on the online (second) edition that’s available for free. I started in on this book last year, but I haven’t been posting about it because I hadn’t gotten to any interesting parts. Now I finally have.
After I solved this problem, I really felt that this scene from The Matrix, “There is no spoon” (video), captured the experience of what it was like to finally realize the solution. First realize the truth, that “there is no spoon”–separate form from appearance (referring to Plato’s notion of “forms”). Once you do that, you can come to see, “It is not the spoon that bends. It is only yourself.” I know, I’m gettin’ “totally trippin’ deep, man,” but it was a real trip to do this problem!
This exercise is an interesting look at how programmers such as myself have viewed how we should practice our craft. It starts off innocuously:
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 an iterative process.
(Update 5-22-2010: Don’t read too much into the “cross-outs” I’m using. I’m just trying to be more precise in my description.) Writing it recursively is pretty easy. You just do a translation from the mathematical classical algebraic notation to Scheme code. It speaks for itself. The challenging part is writing the same thing a solution that gives you the same result using an iterative process. Before you say it can’t be done, it can!
I won’t say never, but you probably won’t see me describing how I solve any of the exercises, because that makes it too easy for CS students to just read this and copy it. I want people to learn this stuff for themselves. I will, however, try to give some “nudges” in the right direction.
- I’ll say this right off the bat: This is not a (classical) mathematical an algebra problem you’re dealing with. It’s easy to fall into thinking this, especially since you’re presented with some algebra as something to implement. This is a computing problem. I’d venture to say it’s more about the mathematics of computing than it is about algebra. As developers we often think of the ideal as “expressing the code in a way that means something to us.” While this is ideal, it can get in the way of writing something optimally. This is one of those cases. I spent several hours trying to optimize the math algebraic operations, and looking for mathematical patterns that might optimize the recursive algorithm into an iterative one. Most of my mathematical the patterns I thought I had fell to pieces. It was a waste of time anyway. I did a fair amount of fooling myself into thinking that I had created an iterative algorithm when I hadn’t. It turned out to be the same recursive algorithm done differently.
- Pay attention to the examples in Section 1.2.1 (Linear Recursion and Iteration), and particularly Section 1.2.2 (Tree Recursion). Notice the difference, in the broadest sense, in the design between the recursive and iterative algorithms in the sample code.
- As developers we’re used to thinking about dividing code into component parts, and that this is the right way to do it. The recursive algorithm lends itself to that kind of thinking. Think about information flow instead for the iterative algorithm. Think about what computers do beyond calculation, and get beyond the idea of calling a function to get a desired result.
- It’s good to take a look at how the recursive algorithm works to get some ideas about how to implement the iterative version. Try some example walk-throughs with the recursive code and watch what develops.
- Here’s a “you missed your turn” signpost (using a driving analogy): If you’re repeating calculation steps in your iterative algorithm, you’re probably not writing an iterative procedure. The authors described the characteristics of a recursive and an iterative procedure earlier in the chapter. See how well your procedure fits into either description. There’s a fine line between what’s “iterative” and what’s “recursive” in Scheme, because in both cases you have a function calling itself. The difference is in a recursive procedure you tend to have the function calling itself more than once in the same expression. Whereas In an iterative procedure you tend to have a simpler calling scheme where the function only calls itself once in an expression (though it may call itself once in more than one expression inside the function), and all you’re doing is computing an intermediate result, and incrementing a counter, to input into the next step. You should not have operators which are “lingering”, waiting for a function call to return, as a rule, though they did show an example earlier of a function that was mostly iterative, with a little recursion thrown in now and then. With this exercise I found that I was able to find a solution that was strictly iterative.
- As I believe was mentioned earlier in this chapter (in the SICP book), remember to use the parameter list of your function as a means for changing state.
- I will say that both the recursive and the iterative functions are pretty simple, though the iterative function uses a couple concepts that most developers are not used to. That’s why it’s tricky. When I finally got it, I thought, “Oh! There it is! That’s cool.” When you get it, it will just seem to flow very smoothly.