Tracing recursive function in paper

Question

I am learning recursion nowadays and as the saying goes, the best way to get proficient in recursion is to practice as much as possible. I have a habit of tracing the program in paper (I guess all of us had at some point).

For example, If I had a function like printing a number from 1 to 10:

def print_n():
    for i in range(1,11):
        print i

I would trace like:

i
.......
1
2
3
4
... and so on

But when I am practicing with recursion, I am finding hard time tracing the program in paper. Can somebody recommend with example a best way to trace recursive function in paper? You can use the following Fibonacci (again!!!) to illustrate your example or you might surprise the readership.

#RECURSIVE FUNCTION TO RETURN Nth FIBONACCI NUMBER
def fib(n):
    if n is 0 or n is 1:
        return 1
    else:
        return fib(n-1) + fib(n-2)

Answer 1

Just throwing this answer in here. I used debuggers a lot, in my development, and they've helped me a lot too. So, I recommend this, because they can often be more helpful, than just printing out strings on the recursion depth.

What I would do when I wanted to trace a recursive function (just wrote a recursive answer here), is that I'd set break points as specific points.

Ideally, most debuggers will allow you to see a list of values that are relevant to the current scope, and allow you to step into a function call to see how it runs.

What I usually do, is create a watchlist of the variables that are important to me. What I do then, is create a diagram of function calls. Very similar to the diagrams created on this website, for example.

My best way to deal with recursion has been to use a debugger bundled with pen and paper. Or if your debugger supports static watchlists, then you don't even need to do that at times. However, I would like to say that at the beginning, its best to sketch things out with pen and paper, since it gives you a better understanding overall of how your program works. Sometimes, people just use recursion and expect the computer to solve the problem for them, and thats awesome, however, its imperative, that you know how your recursion works, and for that (for a beginner) pen and paper are your best tools.

Answer 2

Here is how I would probably put this down on paper, fib(5) shown below:

                                          fib(5)
                       fib(4)               +                  fib(3)
              fib(3)     +      fib(2)      +         fib(2)     +   fib(1)   
     fib(2)     + fib(1) + fib(1) + fib(0)  +    fib(1) + fib(0) +     1
fib(1) + fib(0) +   1    +   1    +   1     +      1    +   1    +     1
  1    +   1    +   1    +   1    +   1     +      1    +   1    +     1