Recursion Tree:

This is the continuation of the previous article about recursion. If you have not already read it, please find it here: https://pramithasdhakal.com/intuitive-introduction-to-recursion

Fibonacci series:

Now, that you have gone through the previous article, lets move ahead with recursion trees.

Let's try to understand them using the famous Fibonacci series.

In this series, every integer is equal to the sum of two integers immediately before it excluding the first two which are fixed.

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, .....

Why Fibonacci series is recursive in nature?

Suppose, I want to calculate 10th Fibonacci number. I know what 10th Fibonacci number is the sum of 9th and 8th Fibonacci number. 9th Fibonacci number is in turn sum of 8th and 7th Fibonacci number and so on. So, for calculating Fibonacci number at each position we are just repeating the same calculation i.e. finding the sum of two number immediately before it.

Expressing above logic in code looks like this:

public int fib(int num){

    if (num == 0){
        return 0;
    }

    if (num == 1){
        return 1;
    }

    int left =  fib(num - 1);
    int right = fib(num - 2);
    return left + right;
}

For position 0 and 1, we are returning 0 and 1 respectively. Otherwise, we are finding the two preceding numbers recursively, adding them and returning to the parent function.

🤯 Understanding the recursion tree:

Here, is the recursive tree for fib(5).

Few things to keep in mind to understand the recursion tree:

1) Execution Direction:

The code execution goes top to bottom until the base condition is met. This means, fib(5) calls fib(4), fib(4) calls fib(3), fib(3) calls fib(2) and fib(2) calls fib(1) where base condition is met. Then, fib(1) returns 1 to fib(2) i.e. the function returns. Then, fib(2) calls fib(0) which is another base condition which returns 0. Then, fib(2) add them to get 1 ( 0+1 ) and returns the value to fib(3) function.

Visualize that the above function is being executed in each of the node. Just the parameter passed to the function is different.

2) Execution Order:

Left nodes are called first. Only after the left nodes are exhausted, right nodes are called.

Please refer to the above diagram to understand the execution order.

One important thing to understand is that the left and right children of a node are not called consecutively. Thus, fib(5) does not call fib(4) and fib(5) consecutively. fib(5) calls fib(4) immediately but fib(3) is called later on only after fib(4) returns.

This can be understood more clearly looking at the source code. Let's examine this section particularly:

int left =  fib(num - 1); // for num = 5, fib(4)
int right = fib(num - 2); // for num = 5, fib(3)

Here, we can see that second line of code is called only after the first line returns as I explained earlier. Hence, fib(5) cannot call fib(3) immediately called after calling fib(4)).

3) Base Condition:

Recursive function reaches the base condition when it knows what value to return to the calling function.

In the above code, the base conditions are represented by the two if conditions.

In the recursive tree, the node having no children represents the base condition. It just means that after that point, no recursive call were made i.e. one of the two if conditions were met.