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)andfibonacci(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.
What did you think?