Recursion Tree
A Recursion Tree is a tree structure that represents the recursive calls made during the execution of a recursive algorithm. Each node represents a single recursive call and its children represent the subsequent recursive calls made within it. This tree aids in understanding and analyzing the time complexity of recursive algorithms.
 Nodes represent individual recursive calls.
 The tree structure helps in analyzing time complexity.
 Useful for understanding recursive algorithms like mergesort, quicksort, etc.
A visual can make understanding recursion trees much clearer. Imagine we’re evaluating a recursive algorithm to compute fibonacci(3)
. The recursion tree would look something like this:
fibonacci(3)
/ \
fibonacci(2) fibonacci(1)
/ \ \
fib(1) fib(0) 1
\ \
1 0
 The root node
fibonacci(3)
splits into two child nodes:fibonacci(2)
andfibonacci(1)
.  The node
fibonacci(2)
further splits intofibonacci(1)
andfibonacci(0)
.  Each node with
fibonacci(0)
orfibonacci(1)
does not have child nodes, representing the base cases of the recursion.
This visualization helps to understand how the function calls itself and why this approach has a time complexity of O(2^n) for the naive Fibonacci implementation. It shows the overlap and redundancy in the recursive calls, motivating the use of techniques like dynamic programming to optimize it.
Code Examples
While we can’t directly implement a recursion tree in code, understanding it will help in analyzing recursive algorithms. Below are examples of simple recursive functions in Java, C++, and Python. Visualizing their recursion tree will help you understand the algorithm’s time complexity.
Java
In Java, the Fibonacci sequence can be computed using recursion. Below is a simple code snippet.


C++
Similarly, in C++, you can compute the factorial of a number using recursion.


Python
In Python, you can find the sum of an array using recursion.


Understanding the recursion tree of these algorithms can help in deriving their time complexity and improving their efficiency.