Recursive Fibonacci

Recursive

Compute F(n) = F(n−1) + F(n−2) straight from the definition; the call tree shows why this is exponential.

The Fibonacci definition is recursive itself: F(0) = 0, F(1) = 1 and F(n) = F(n−1) + F(n−2). Translating it straight into code is easy but very slow.

Read the full explanation ↓

Time: O(φⁿ) ≈ O(1.618ⁿ)
Space: O(n)
Johnsonbaugh, chapter 4
CLRS, chapter 14

Input:

n=5PDF export

F(5) = 5 with 15 calls; F(2) is computed three separate times.

def fib(n):
if n < 2:
return n
left = fib(n - 1)
right = fib(n - 2)
return left + right

Invariant: Every call FIB(k) returns exactly F(k); but FIB(k) for small k is computed again and again.

Start

left—

right—

Recursion tree

Filled orange = running call · Orange outline = still on the stack · Grey = finished

Local variables

Orange = changed in this step

Call stack

fib()line 1

Step 1 of 59

Explanation

The idea

The Fibonacci definition is recursive itself: F(0) = 0, F(1) = 1 and F(n) = F(n−1) + F(n−2). Translating it straight into code is easy but very slow.

Why exponential?

FIB(n) calls both FIB(n−1) and FIB(n−2); but FIB(n−1) calls FIB(n−2) again. The subproblems overlap, and each is solved again and again. The number of calls is 2·F(n+1) − 1, about 1.618ⁿ.

The fix

With memoization (storing answers) or dynamic programming (filling a table bottom up), each F(k) is computed once and the time drops to O(n).

What to watch in the trace

Look at the call tree: repeated branches such as FIB(2) show up many times.
The call stack is at most n deep, so the memory is O(n).