Thursday, 5 February 2015

Tracing Recursion: Thinking like a computer.

I like recursion. I don't know why it appeals to me- I just do. In fact, I used recursion in order to code the RPN calculator for the second lab. Without giving away too much, I made a method which would evaluate both operands and the operator of a binomial (written in RPN, of course). If the latter operand was itself a binomial, it would call itself to further break down the binomial into two operands and an operator. And than it keeps doing this until the most deeply nested binomial is broken down, and than evaluates all of them in that order. If I get permission from a TA, I'll post the code for it later on.

Anyways, to get back on topic,I find that tracing recursive code isn't all that different from tracing any other code- provided, of course, that you are used to the concept of recursion. All you need to do is constrain your thinking and just mindlessly follow the steps, without thinking about what the code is actually trying to accomplish. After all, this is what python does. It doesn't know what your program is trying to accomplish- even if it has a name like "count_list_depth". All it knows is that it has to follow the steps, no matter where they go. In a strange way, this is exactly how not to begin writing a program. Usually, if a programmer is needed, the problem isn't so simple that a small sequence of instructions can solve it. Usually, a sort of outline of the problem has to be devised, before any sort of solution can be attempted. Long story short- we need to be thinking at a high level of abstraction. Its not enough to know how to solve one or two parts of it- we need a skeleton which can account for everything. Only than can the details pertaining to implimentation be sorted out.

Anyways, I found the recursion tracing exercises to be surprisingly pleasant, and an invaluable source of practice. If I could give anyone advice though, it would be to get used to the syntax of recursive code- especially when it comes to list comprehensions. Worst comes to worst, you learned a new and more compact way to code list objects...


  1. you can always post code to lab exercises :)

  2. This comment has been removed by the author.