Fibonacci: Recursion & Exponential Complexity

The Recursive Approach: A Direct Translation

The Fibonacci sequence is defined by the recurrence relation:

with the base cases typically defined as $F_0=0$ and $F_1=1$.

Given your comfort with C++, you can see that this mathematical definition translates almost directly into a recursive function. A function to calculate $F_n$ will call itself to calculate $F_{n-1}$ and $F_{n-2}$ and then sum their results. The recursion stops when it hits the base cases.

Let's examine a straightforward implementation and an initial analysis of its performance.

The code you just reviewed is a perfect example of translating a recurrence relation into a program. It's clean, readable, and correct. However, as we hinted in the last lesson, its performance is a critical issue.

Visualizing the Redundancy: The Recursion Tree

The inefficiency stems from the "overlapping subproblems" property. A naive recursive implementation re-computes the same Fibonacci numbers over and over again. The best way to see this is by drawing the recursion tree for the function calls.

As the diagram illustrates, computing f(n) requires f(n-1) and f(n-2). The call to f(n-1) then generates its own sub-problems, including f(n-2) and f(n-3). But wait—we already needed to compute f(n-2) for our original f(n) call! The function is blindly re-doing work. As n grows, this redundant work explodes.

To see this process animated, the following video provides an excellent step-by-step visualization for fib(4).

Quantifying the Inefficiency: Time Complexity Analysis

Now that we have the intuition, let's formally analyze the time complexity. Since you appreciate theoretical rigor, we'll approach this from a couple of angles.

1. Analysis via Recurrence Relation

Let $T(n)$ be the time taken to compute Fibonacci(n). We can model this with a recurrence relation that mirrors the code's structure:
$T(n)=T(n-1)+T(n-2)+c$
Here, $T(n-1)$ and $T(n-2)$ are the costs of the two recursive calls, and $c$ represents the constant-time work done within the function (two comparisons and one addition). For our base cases, $T(0)$ and $T(1)$ are constant, or $O(1)$.

This recurrence is notoriously difficult to solve exactly, but we can find a solid upper bound. Since $T(n-2)<T(n-1)$, we can say:
$T(n)=T(n-1)+T(n-2)<T(n-1)+T(n-1)=2T(n-1)$
So, we have $T(n)<2T(n-1)$. If we unroll this inequality:
$T(n)<2\cdot (2T(n-2))=4T(n-2)<8T(n-3)<\cdots <2^{n-1}T(1)$
Since $T(1)$ is a constant, this simplifies to $T(n)\in O(2^n)$. The time complexity is exponential.

The following video provides a clear walkthrough of this exact derivation.

2. The Tangible Impact of Exponential Growth

What does $O(2^n)$ mean in practice? Let's return to the studyplan.dev article, which provides some shocking numbers by simply adding a counter to the function.

A calculation for n=40 taking hundreds of millions of operations would time out instantly in a competitive programming contest, where you typically have a budget of around $10^8$ operations per second. This demonstrates that the naive recursive solution is not viable.

A Tighter Bound (For the Curious)

For a problem with a recurrence like $T(n)=T(n-1)+T(n-2)$, the number of operations is, in fact, proportional to the $n$-th Fibonacci number itself. The closed-form solution for Fibonacci numbers involves the golden ratio, $\varphi \approx 1.618$.

Therefore, a tighter bound on the complexity is $O({\varphi }^n)$. While we still write this as $O(2^n)$ for a simpler and valid upper bound, it's useful to know that the base of the exponent is smaller than 2. This is because the recursion tree is not a "full" binary tree; one branch is always shorter than the other (n-2 vs. n-1), as explained in the Kantan Coding video. If you're interested in the math behind the golden ratio connection, the Stack Overflow thread below provides several excellent derivations.

Conclusion

In this lesson, we took a concrete problem that exhibits overlapping subproblems and implemented the most direct solution. We've now seen firsthand, through visualization and formal analysis, how this leads to disastrous exponential time complexity.

Key Takeaways:

• A direct recursive implementation of the Fibonacci sequence is a classic example of translating a mathematical recurrence into code.
• The recursion tree for this function clearly visualizes the massive number of redundant computations, which is the hallmark of overlapping subproblems.
• The time complexity can be described by the recurrence $T(n)=T(n-1)+T(n-2)+c$.
• By finding an upper bound, we proved that the time complexity is $O(2^n)$, which is prohibitively slow for non-trivial inputs.

You now understand the "disease" of overlapping subproblems in detail. In our next lesson, we will introduce the "cure": memoization. We will modify our simple recursive code to cache the results of subproblems, drastically improving its performance from exponential to linear time.