fibonacci.py

# Three implementations of Fibonacci with timing comparison.
# Demonstrates the difference between recursive, iterative, and memoized approaches.

from timeit import Timer


# --- Recursive ---
# Each call spawns two more calls. Exponential time complexity O(2^n).
# Very slow for large n due to repeated recalculation of the same values.

def fib(n):
    if n == 0:
        return 0
    elif n == 1:
        return 1
    return fib(n - 1) + fib(n - 2)


# --- Iterative ---
# Maintains only the last two values, updating in each step.
# Linear time O(n), constant space O(1).

def fib_iterative(n):
    if n == 0:
        return 0
    old, new = 0, 1
    for _ in range(n - 1):
        old, new = new, old + new
    return new


# --- Memoized (top-down dynamic programming) ---
# Stores previously computed values to avoid redundant calls.
# Linear time O(n), linear space O(n).

memo = {0: 0, 1: 1}

def fib_memo(n):
    if n not in memo:
        memo[n] = fib_memo(n - 1) + fib_memo(n - 2)
    return memo[n]


# --- Timing comparison ---

def compare(max_n=35):
    print(f"{'n':>4}  {'recursive':>12}  {'iterative':>12}  {'memoized':>12}")
    print('-' * 46)
    for n in range(1, max_n + 1):
        t_rec  = Timer(f'fib({n})',      'from __main__ import fib').timeit(3)
        t_iter = Timer(f'fib_iterative({n})', 'from __main__ import fib_iterative').timeit(3)
        t_memo = Timer(f'fib_memo({n})', 'from __main__ import fib_memo').timeit(3)
        print(f'{n:>4}  {t_rec:>12.6f}  {t_iter:>12.6f}  {t_memo:>12.6f}')


if __name__ == '__main__':
    print('Fibonacci values (first 10):')
    for i in range(10):
        print(f'  fib({i}) = {fib(i)}')

    print()
    print('Timing comparison (seconds for 3 runs):')
    compare()