What is Tree Recursion? (Fibonacci example)
In linear recursion (like Factorial), a function makes at most one recursive call per execution frame. In Tree Recursion, a function makes multiple recursive calls per frame. This branches out, forming a tree-like execution graph.
The Fibonacci recurrence relation is:
fib(N) = fib(N - 1) + fib(N - 2)
This triggers two recursive calls at each step, except for base cases:
- Base Cases:
fib(0) = 0andfib(1) = 1. - Recursive Case:
fib(n) = fib(n-1) + fib(n-2).
Overlapping Subproblems
If you inspect the recursion tree, you will notice that the same state is calculated multiple times. For example, to calculate fib(4):
fib(2)is calculated 2 times.fib(1)is calculated 3 times.
As $N$ grows, the number of redundant computations grows exponentially. This can be optimized using Memoization (caching results) or Dynamic Programming (iterative solutions) to reduce time complexity from exponential to linear.
Complexity Analysis
Time Complexity: O(2^N)
Specifically, the number of operations is proportional to the Golden Ratio raised to $N$ power, approx. $1.618^N$, which is mathematically bounded by $O(2^N)$ representing exponential growth.
Space Complexity: O(N)
Even though the total number of calls is exponential, the Call Stack only holds active frames. The maximum stack depth is bounded by the height of the tree, which is linear, $O(N)$.