6

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)
Improve this question
6
  • 3
    Actually, the best way to get proficient at recursion is to get proficient at recursion. Commented Oct 29, 2013 at 20:05
  • 1
    I think I am reading so much about recursion these days that the joke you just told is old. Commented Oct 29, 2013 at 20:05
  • 2
    emunix.emich.edu/~haynes/Papers/Recursion/recursion.html Commented Oct 29, 2013 at 20:06
  • @gtgaxiola: nice link Commented Oct 29, 2013 at 20:07
  • 1
    I'm writing one that involves a debugger. Hope you can wait to see it. Commented Oct 29, 2013 at 20:12

4 Answers 4

Reset to default
8

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.

enter image description here

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.

Improve this answer
Sign up to request clarification or add additional context in comments.

6 Comments

Checked the web-link! Great job! Really liked it.
@Jack_of_All_Trades If you could wait just a little longer, I'll show you some of my diagrams.
@Jack_of_All_Trades Take a look at the answer now, should make things clearer. I did not expand on 3, because there was no need to, as 4 would expand to 3 anyways :P
@Jack_of_All_Trades Glad you liked it, I drew that with a graphics tablet.
Which debugger are you using for Python 3?
|
6

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
Improve this answer

1 Comment

Thanks for this answer! Great visual representation
4

Let the computer do the heavy lifting for you! By adding a few lines you can watch how the function dives in recursively:

def fib(n,depth=0):
    print ''.join(["*"]*depth), n

    if n is 0 or n is 1:
        return 1
    else:
        return fib(n-1,depth+1) + fib(n-2,depth+1)

fib(5)

Gives:

 5
* 4
** 3
*** 2
**** 1
**** 0
*** 1
** 2
*** 1
*** 0
* 3
** 2
*** 1
*** 0
** 1

Note that we are tracking the depth in addition to n now. In this case it's easy to see how depth and n are related, but in other cases it might not be so obvious so this exercise is not completely academic. We print out a visual representation of depth by the line ''.join(["*"]*depth) which simply creates a string of *'s the same size of depth.

Improve this answer

1 Comment

thanks for the clever use of letting program do the heavy-lifting.
4

It would go like this:

fib(3)
 n=3 so return fib(2) + fib(1)

So now we need fib(2) and fib (1)

   fib(2)
    n =2 so return fib(1)+fib(0)
    fib (1)
     n=1 so return 1

    fib (0) 
     n=0 so return 1

    Now we can have fib(2) return 1+1 = 2. We still need to do fib(1) to return the value of fib(3)

    fib(1)
     n=1 so return 1

Now we can return fib(3)'s value of 2+1=3
Improve this answer

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.