Problem

The Fibonacci sequence is defined as: F(0) = 0, F(1) = 1, and F(n) = F(n-1) + F(n-2) for n > 1. Given an integer n, return F(n).

Example

Input:  n = 10
Output: 55
Sequence: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55

Solution: Iterative (Best)

The naive recursive solution recalculates the same values exponentially many times. The iterative approach computes each value once.

def fib(n):
    if n < 2:
        return n
    a, b = 0, 1
    for _ in range(n - 1):
        a, b = b, a + b
    return b

function fib(n) {
    if (n < 2) return n;
    let a = 0, b = 1;
    for (let i = 0; i < n - 1; i++) {
        [a, b] = [b, a + b];
    }
    return b;
}

int fib(int n) {
    if (n < 2) return n;
    int a = 0, b = 1;
    for (int i = 0; i < n - 1; i++) {
        int temp = a + b;
        a = b;
        b = temp;
    }
    return b;
}

public int fib(int n) {
    if (n < 2) return n;
    int a = 0, b = 1;
    for (int i = 0; i < n - 1; i++) {
        int temp = a + b;
        a = b;
        b = temp;
    }
    return b;
}

Solution: Recursive with Memoization

If you must use recursion, cache results to avoid redundant computation.

from functools import lru_cache

@lru_cache(maxsize=None)
def fib(n):
    if n < 2:
        return n
    return fib(n - 1) + fib(n - 2)

const memo = new Map();
function fib(n) {
    if (n < 2) return n;
    if (memo.has(n)) return memo.get(n);
    const result = fib(n - 1) + fib(n - 2);
    memo.set(n, result);
    return result;
}

Complexity Comparison

• Naive recursion: O(2^n) time — way too slow for large n
• Memoized recursion: O(n) time, O(n) space (recursion stack + cache)
• Iterative: O(n) time, O(1) space — the winner

Why Iterative Wins

Both the iterative and memoized solutions have O(n) time complexity, but iterative wins on memory. We don’t need to remember all Fibonacci numbers up to n — only the last two. This drops space from O(n) to O(1). This is a classic example of dynamic programming optimization: identifying that you only need a small “window” of previous results, not all of them.