PyOhio, Recursive Fibonacci, and Recursion Trees

My proposal to PyOhio was accepted (and ranked in the top 20 of around 100 submitted proposals) and I have been working hard to prepare my talk on recursion.

A question was posed to me recently about the seemingly bizarre order that the recursive Fibonacci solution follows when calculating a number in the sequence.

Allow me to explain. Let's say that this is our solution in Java: 

public static int fib(int n)
{
int result = -1;
//base case 1
if (n == 0)
{
result = 0;
}
//base case 2
else if(n==1)
{
result = 1;
}
//recursive case
else
{
result = fib(n-1) + fib(n-2);
}
return result;
}

Now, let's say that we want to keep track of the flow of execution of the program. To do this, I'll write statements to print lines telling us which number in the Fibonacci sequence we're trying to calculate at that point in the code. 

The code will look like this now:

public static int fib(int n)
{
int result = -1;
//base case 1
if (n == 0)
{
System.out.println("Computing fib("+n+")");
result = 0;
}
//base case 2
else if(n==1)
{
System.out.println("Computing fib("+n+")");
result = 1;
}
//recursive case
else
{
System.out.println("Computing fib("+n+")");
result = fib(n-1) + fib(n-2);
}
return result;
}

When I ran that code, the output seemed bizarre at first. Here's what it looks like when n=5.

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

This had me stumped. I realized that when my code got to the recursive call, it would try to calculate fib(n-1) which would require a require recursive call and the process would get repeated, but eventually it would also need to call fib(n-2). I tried creating a spreadsheet to keep track of whether I was calculating "n-1" or "n-2," but it got messy and confusing.

I had learned about recursion trees before and drew one because I thought it might be helpful, but I mostly ignored it because in my mind I was separating the way a recursion tree works from the way code is executed.

However, after getting frustrated enough, I drew a recursion tree again and this time I tried to label the spots on the tree to match the order of computations and it made so much sense after I did it!

I've included the image of my recursion tree for fib(6) below.

If it does not make sense to you, that is perfectly all right! This was a very brief explanation. I may explain this in more detail in a future talk I give or in response to any questions posed by my readers. Feel free to comment with questions!

Comments