Debugging recursion in a systematic way

At the end of this slog http://tracycsc148.blogspot.ca/2014/02/csc148-slog-object-oriented-programming.html, the author mentioned “a recursive function will not stop running until the condition in the 'else' part is met” which sounds easy to understand but actually hard to recognize such an error when actually coding. So here I am about to talk about how I debug for recursive functions.

               First of all, the most obvious one – syntax error. It’s obvious doesn’t mean it’s always easy to recognize. Like the preorder function for Trees,

(This is not quite right. Please refer to CSC148 website for the correct version)

When brackets and parenthesis get mixed up, it became much harder to detect where we missed a right parenthesis or a bracket at a glimpse and it’s very likely that we need spend quite a while reading line by line if coding larger projects. Such thing is inevitable but we can always try to avoid it by splitting them into different blocks – instead of writing ternary if, writing in different blocks as we did in CSC108 makes such ‘silly’ error more apparent and may save much time.

               Then comes to the run-time error where under most circumstances problems occur. Most people trying to write recursive function must have experienced error message like ‘Maximum recursion depth exceeded’ which indicated the program falls into an infinite loop. To fix such an error, the very first thing, to me, is to test the base case – an infinite loop always mean the program can’t get to the base case or the base case is in an infinite loop. So it is essential to trace the base case and make sure it’s functioning. For instance of the Fibonacci sequence I wrote in my previous slog (http://siyangcsc148w3.blogspot.ca/2014/01/some-thoughts-on-recursion.html), a functioning base case is essential for keeping the program getting into infinite loop. After the base case, check the constructor cases. Starting from small cases, like the third element in Fibonacci sequence and print out things returned by every recursive step. Still, I will take my fib function as an example.

What I did is to print tuples made up of the fib result and its associated number.

Suppose I type fib(4), it will print (1,2) and (1,1) ,(2,3)and return 2. So I will know fib(2) , fib(1) and fib(3) are all working and if it’s not working, I could quickly find out at which point the recursion failed and fix it.

I used this method in Assignment 1 where Tour module worked for 8,9,10 and 11 cheeses but not for 12 cheeses. As I print out all the recursion steps, I found my initial set up for 2 cheeses is wrong where I set i=0 for 2 cheeses instead of 1. And it saves huge amount of time than tracing by hand or wondering around.