Algorithm

Fibonacci

Recursion Pattern

Fibonacci

The Fibonacci sequence starts 0, 1, and every later term is the sum of the two before it: 0, 1, 1, 2, 3, 5, 8, 13, … Given a non-negative integer n, return the n-th Fibonacci number, where fib(0) = 0 and fib(1) = 1. Return the single integer. Write it as a direct recursion so the branching call tree is visible — then see why that tree is a problem.

CONSTRAINTS
  • 0 <= n <= 30 (naive recursion becomes slow well before this)
  • fib(0) = 0, fib(1) = 1
  • The result fits comfortably in a 32-bit integer for n ≤ 30
EXAMPLE 1
Input: n = 0
Output: 0
fib(0) is the anchored first value, 0. Base case.
EXAMPLE 2
Input: n = 1
Output: 1
fib(1) is the anchored second value, 1. Base case.
EXAMPLE 3
Input: n = 5
Output: 5
The sequence 0,1,1,2,3,5 — the term at index 5 is 5.
EXAMPLE 4
Input: n = 10
Output: 55
0,1,1,2,3,5,8,13,21,34,55 — index 10 is 55. Even this small n causes many repeated sub-calls under naive recursion.
Why are there two base cases here but only one for factorial?
The recurrence looks back two steps (n − 1 and n − 2), so the recursion bottoms out on two values, fib(0) and fib(1). The single test n ≤ 1 covers both and returns n, which happens to be correct for both.
Is fib(0) = 0 or 1?
This problem defines fib(0) = 0 and fib(1) = 1, the most common convention. Some sources start 1, 1 — always confirm the indexing in an interview, since it shifts every answer.
Why is the naive version considered bad if it is correct?
Correctness is not the issue — cost is. It recomputes the same subproblems exponentially many times, so it is O(2ⁿ). The fix is memoization (the next problem), which reuses each result.
Could I just use a loop?
Yes — an iterative version tracking the last two values is O(n) time and O(1) space. The naive recursion is shown to expose the overlapping-subproblem waste that motivates memoization and dynamic programming.

Fibonacci is defined by its own two predecessors: fib(n) = fib(n − 1) + fib(n − 2), starting from fib(0) = 0 and fib(1) = 1. The definition is recursive on its face, so the code almost writes itself — and that is exactly the trap. This problem introduces binary recursion: a function that calls itself twice, turning the straight chain from Factorial into a branching tree.

Translating the definition directly

There are two base cases this time (n = 0 and n = 1), because the recurrence reaches back two steps and needs two anchored starting values. Then the recursive case adds the two smaller answers:

python
def fib(n):
    if n <= 1:                 # two base cases folded into one test: fib(0)=0, fib(1)=1
        return n
    return fib(n - 1) + fib(n - 2)   # TWO recursive calls — this branches

The leap of faith is the same as before: trust that fib(n − 1) and fib(n − 2) each return the right value, and just add them. It is correct. The catastrophe is in what it costs.

Where the waste is: the same work, over and over

With one recursive call (Factorial), the calls form a line. With two, each call spawns two more, which spawn two more — a binary tree of calls that roughly doubles in size at every level. Worse, the two branches overlap and recompute the same values independently. Watch fib(5) start to expand:

text
fib(5) = fib(4) + fib(3)
fib(4) = fib(3) + fib(2)      <- fib(3) is now being computed twice
fib(3) = fib(2) + fib(1)      <- fib(2) computed again... and again...

fib(3) is computed 2 times, fib(2) is computed 3 times, fib(1) even more — and none of them remember each other's work. The number of calls grows like the Fibonacci numbers themselves, which is roughly O(2ⁿ) — exponential. fib(30) already triggers over a million calls; fib(50) would take longer than you will wait. The recursion is correct but does an astronomical amount of duplicated work.

Worked Example:the call tree for fib(4)
- fib(4) asks for fib(3) and fib(2).
- fib(3) asks for fib(2) and fib(1). fib(2) asks for fib(1) and fib(0).
- So across the whole tree: fib(2) is evaluated twice (once under fib(4), once under fib(3)), fib(1) is evaluated three times, fib(0) twice. Every one of those is a full, independent call.
- The values returned are correct — fib(4) = 3 — but the tree has 9 calls to produce a number we could reach in 4 additions by hand.
Key Insightthe cost of a recursion is the size of its call tree, not the value of n. One recursive call gives a linear chain (cheap); two overlapping calls give an exponential tree (ruinous). Counting the tree, not eyeballing the code, is how you judge a recursion's cost.
What this problem is really teaching

Fibonacci is the canonical example of overlapping subproblems: the same smaller inputs are solved again and again across different branches. The recursion itself is not the villain — the forgetting is. The moment you notice a recursive function recomputing an input it has already solved, there is a fix: remember each answer the first time and look it up thereafter. That single idea collapses the exponential tree back into a linear walk, and it is important enough to be its own problem: Fibonacci (Memoized), next. Recognizing overlapping subproblems is also the exact doorway from recursion into dynamic programming — DP is, at heart, recursion plus memory.

O(2ⁿ) Time · O(n) Stack Naive Recursion
→
O(n) Memoized Recursion