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)
- fibonacci(5) is called at the top.
- After that, it generates two recursive calls
- 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.