Explain Recursion Tree in Algorithm with Example

by

A recursion tree visually represents the recursive calls made in a recursive algorithm. It helps to illustrate how the recursive function is called at each step. However, We know that a tree has a node and here each node represents a recursive call.

Let’s understand the concept of a recursion tree with Fibonacci sequence

The Fibonacci series consist number sequence in which each number is the sum of the two preceding numbers. We can find the Fibonacci numbers using a recursive approach.

Recursive function for Fibonacci series

def fibonacci(n):
    if n <= 1:
        return n
    else:
        return fibonacci(n - 1) + fibonacci(n - 2)

# Compute the 5th Fibonacci number
print(fibonacci(5))

In the above example, fibonacci(5) will make recursive calls to calculate the Fibonacci sequence up to the 5th number.

Recursion Tree for fibonacci series:

                       fibonacci(5)
                     /             \
          fibonacci(4)              fibonacci(3)
         /             \             /             \
fibonacci(3)   fibonacci(2)     fibonacci(2)   fibonacci(1)
/             \
fibonacci(2)   fibonacci(1)

Explanations

  • fibonacci(5) is called at the top.
  • After that, it generates two recursive calls fibonacci(4) and fibonacci(3).
  • Every time newly generated recursive calls generate new calls until we reach the base case (n <= 1). In the base case, the function returns a specific value.
  • As we go down the recursion tree, the number of recursive calls increases.
  • Once the base case has reached, the recursion stops, and the function starts combining the results from the lower levels to obtain the final Fibonacci number in an upward direction.