# Explain Recursion Tree in Algorithm with Example

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.