Why is computing the Fibonacci sequence directly via recursion highly inefficient?

Conditions

• The algorithm uses naive recursion without memoization.
• The recurrence relation is $f(n) = f(n-1) + f(n-2)$.

Reasoning, step by step

1. Construct the recursion tree for a target computation like $f(7)$.
2. Trace the branches downward to observe the generated subproblems.
3. Identify that the same subproblem (e.g., $f(4)$) appears multiple times in different branches.
4. Conclude that the algorithm redundantly recalculates these overlapping subproblems, leading to exponential time complexity.

Example

As the tree grows downward, it becomes clear that nodes such as $f(4)$, $f(3)$, and $f(2)$ are repeatedly generated across different branches. This visual process profoundly reveals the extensive redundant computation inherent in the naive recursive algorithm.

Common misconceptions

• Beginners may think recursion is simply calling itself, unaware that binary-branching recursion generates exponentially many repeated subproblems.
• Assuming that the recursion tree only contains unique nodes without any overlapping subproblems.

Watch the explanation

Explore next

• How to analyze the time complexity of a recursive algorithm using a recursion tree?
• What is the time complexity of this recursive algorithm?
• How does the video distinguish between practical drawing and theoretical estimation of the tree?