Fibonacci — iterative vs recursive

Problem

Write a function that returns the nth Fibonacci number.

F(0) = 0
F(1) = 1
F(n) = F(n-1) + F(n-2)

Examples:

• fib(6) → 8
• fib(10) → 55

Approach

The naive recursive solution has O(2ⁿ) time — each call branches into two more calls, and the same subproblems get recomputed thousands of times.

The key insight: we only ever need the previous two values. We don't need the full call tree. This means we can go iterative and get O(n) time with O(1) space.

Alternatively, memoization on the recursive version gives O(n) time but O(n) space for the cache.