Memoization

def fib_slow(n):
    """
    Naive recursion - EXTREMELY SLOW!
    Time: O(2^n) - exponential growth
    Space: O(n) - recursion stack depth
    
    Problem: Massive redundant calculations
    fib(5) = fib(4) + fib(3)
           = (fib(3) + fib(2)) + (fib(2) + fib(1))
           = ((fib(2) + fib(1)) + fib(2)) + (fib(2) + fib(1))
    
    fib(2) is calculated 3 times!
    fib(3) is calculated 2 times!
    For fib(40), there are 331,160,281 function calls!
    """
    if n < 0:
        raise ValueError("n must be non-negative")
    if n <= 1:
        return n
    return fib_slow(n - 1) + fib_slow(n - 2)

# Try this - it takes several seconds!
import time
start = time.time()
result = fib_slow(35)
print(f"fib(35) = {result}, took {time.time() - start:.2f}s")
# Output: fib(35) = 9227465, took ~3.5s

import java.math.BigInteger;

public class FibonacciSlow {
    /**
     * Naive recursion - EXTREMELY SLOW!
     * Time: O(2^n) - exponential growth
     * Space: O(n) - recursion stack depth
     * 
     * Problem: Massive redundant calculations
     * fib(5) = fib(4) + fib(3)
     *        = (fib(3) + fib(2)) + (fib(2) + fib(1))
     *        = ((fib(2) + fib(1)) + fib(2)) + (fib(2) + fib(1))
     * 
     * fib(2) is calculated 3 times!
     * fib(3) is calculated 2 times!
     * For fib(40), there are 331,160,281 function calls!
     */
    public static BigInteger fibSlow(int n) {
        if (n < 0) throw new IllegalArgumentException("n must be non-negative");
        if (n <= 1) {
            return BigInteger.valueOf(n);
        }
        return fibSlow(n - 1).add(fibSlow(n - 2));
    }
    
    public static void main(String[] args) {
        // Try this - it takes several seconds!
        long start = System.currentTimeMillis();
        BigInteger result = fibSlow(35);
        double elapsed = (System.currentTimeMillis() - start) / 1000.0;
        System.out.printf("fib(35) = %d, took %.2fs%n", result, elapsed);
        // Output: fib(35) = 9227465, took ~3.5s
    }
}

def fib_memo(n, memo=None):
    """
    Memoization - LIGHTNING FAST!
    Time: O(n) - each number computed once
    Space: O(n) - memo dict + recursion stack
    
    Each fib(k) is computed exactly once and cached
    Subsequent calls return cached value in O(1)
    """
    if n < 0:
        raise ValueError("n must be non-negative")

    # Initialize memo on first call
    if memo is None:
        memo = {}
    
    # Step 1: Check cache first
    if n in memo:
        return memo[n]  # Cache hit - instant return!
    
    # Step 2: Cache base cases too.
    if n <= 1:
        memo[n] = n
        return n
    
    # Step 3: Compute recursively (may use cached values)
    result = fib_memo(n - 1, memo) + fib_memo(n - 2, memo)
    
    # Step 4: Store in cache before returning
    memo[n] = result
    
    return result

# Same calculation, but instant!
import time
start = time.time()
result = fib_memo(35)
print(f"fib(35) = {result}, took {time.time() - start:.6f}s")
# Output: fib(35) = 9227465, took 0.000050s

# Can even handle huge inputs!
print(f"fib(100) = {fib_memo(100)}")
# Output: fib(100) = 354224848179261915075

import java.math.BigInteger;
import java.util.HashMap;
import java.util.Map;

public class FibonacciMemo {
    /**
     * Memoization - LIGHTNING FAST!
     * Time: O(n) - each number computed once
     * Space: O(n) - memo map + recursion stack
     * 
     * Each fib(k) is computed exactly once and cached
     * Subsequent calls return cached value in O(1)
     */
    public static BigInteger fibMemo(int n, Map<Integer, BigInteger> memo) {
        if (n < 0) throw new IllegalArgumentException("n must be non-negative");
        // Step 1: Check cache first
        if (memo.containsKey(n)) {
            return memo.get(n);  // Cache hit - instant return!
        }
        
        // Step 2: Cache base cases too.
        if (n <= 1) {
            BigInteger base = BigInteger.valueOf(n);
            memo.put(n, base);
            return base;
        }
        
        // Step 3: Compute recursively (may use cached values)
        BigInteger result = fibMemo(n - 1, memo).add(fibMemo(n - 2, memo));
        
        // Step 4: Store in cache before returning
        memo.put(n, result);
        
        return result;
    }
    
    public static void main(String[] args) {
        Map<Integer, BigInteger> memo = new HashMap<>();
        
        // Same calculation, but instant!
        long start = System.nanoTime();
        BigInteger result = fibMemo(35, memo);
        double elapsed = (System.nanoTime() - start) / 1_000_000_000.0;
        System.out.printf("fib(35) = %d, took %.6fs%n", result, elapsed);
        // Output: fib(35) = 9227465, took 0.000050s
        
        // BigInteger preserves exact values beyond signed long.
        memo.clear();
        BigInteger expected = new BigInteger("354224848179261915075");
        if (!fibMemo(100, memo).equals(expected)) throw new AssertionError();
    }
}