784 Intermediate

784-fibonacci-memo-tab — Fibonacci: Memoization vs Tabulation

Functional Programming

Tutorial Video

Text description (accessibility)

This video demonstrates the "784-fibonacci-memo-tab — Fibonacci: Memoization vs Tabulation" functional Rust example. Difficulty level: Intermediate. Key concepts covered: Functional Programming. Dynamic programming (DP) is an algorithm design technique from Richard Bellman (1950s) that solves problems by breaking them into overlapping subproblems and storing intermediate results. Key difference from OCaml: 1. **Memoization ergonomics**: OCaml's `Hashtbl.memo` pattern is more concise than Rust's explicit `HashMap`; Rust requires a closure or struct to carry the cache.

Tutorial

The Problem

Dynamic programming (DP) is an algorithm design technique from Richard Bellman (1950s) that solves problems by breaking them into overlapping subproblems and storing intermediate results. Fibonacci is the canonical teaching example: naive recursion recomputes fib(n-2) exponentially many times. Two DP strategies fix this: memoization (top-down, cache on demand) and tabulation (bottom-up, fill a table iteratively). Understanding both is essential for tackling more complex DP problems.

🎯 Learning Outcomes

• Recognize why naive recursive Fibonacci is O(2^n) and understand the overlapping subproblems insight

• Implement top-down memoization using HashMap as a cache

• Implement bottom-up tabulation using a Vec<u64> table filled iteratively

• Implement space-optimized tabulation using only two variables: O(1) space

• Know when to prefer memoization (sparse subproblems) vs tabulation (dense subproblems)

Code Example

pub fn fib_memo(n: u64) -> u64 {
    fn helper(n: u64, cache: &mut HashMap<u64, u64>) -> u64 {
        if let Some(&result) = cache.get(&n) {
            return result;
        }
        let result = match n {
            0 => 0, 1 => 1,
            _ => helper(n - 1, cache) + helper(n - 2, cache),
        };
        cache.insert(n, result);
        result
    }
    helper(n, &mut HashMap::new())
}

let fib_memo n =
  let cache = Hashtbl.create 100 in
  let rec helper n =
    match Hashtbl.find_opt cache n with
    | Some v -> v
    | None ->
        let result = match n with
          | 0 -> 0 | 1 -> 1
          | _ -> helper (n - 1) + helper (n - 2)
        in
        Hashtbl.add cache n result;
        result
  in
  helper n

Key Differences

Memoization ergonomics: OCaml's Hashtbl.memo pattern is more concise than Rust's explicit HashMap; Rust requires a closure or struct to carry the cache.

Lazy evaluation: OCaml's lazy keyword provides built-in memoization for thunks; Rust uses std::sync::OnceLock or once_cell for equivalent functionality.

Tail calls: OCaml's compiler optimizes tail-recursive accumulator patterns; Rust has no guaranteed TCO (though LLVM often optimizes it).

Space optimization: Both languages trivially implement the two-variable space-optimized form; neither requires special syntax.

OCaml Approach

OCaml's functional style naturally encourages memoization via Hashtbl or lazy values. A memoize higher-order function can wrap any recursive function: let memo_fib = memoize (fun f n -> if n <= 1 then n else f (n-1) + f (n-2)). The lazy keyword creates deferred computations that are evaluated once and cached. Tabulation uses Array.init n (fun i -> dp.(i-1) + dp.(i-2)).

Full Source

#![allow(clippy::all)]
//! # Fibonacci: Memoization vs Tabulation
//!
//! Comparing top-down and bottom-up dynamic programming approaches.

use std::collections::HashMap;

// ═══════════════════════════════════════════════════════════════════════════════
// Naive Recursive (exponential time)
// ═══════════════════════════════════════════════════════════════════════════════

/// Naive recursive Fibonacci - O(2^n)
pub fn fib_naive(n: u64) -> u64 {
    match n {
        0 => 0,
        1 => 1,
        _ => fib_naive(n - 1) + fib_naive(n - 2),
    }
}

// ═══════════════════════════════════════════════════════════════════════════════
// Memoization (Top-Down DP)
// ═══════════════════════════════════════════════════════════════════════════════

/// Memoized Fibonacci using HashMap
pub fn fib_memo(n: u64) -> u64 {
    fn helper(n: u64, cache: &mut HashMap<u64, u64>) -> u64 {
        if let Some(&result) = cache.get(&n) {
            return result;
        }
        let result = match n {
            0 => 0,
            1 => 1,
            _ => helper(n - 1, cache) + helper(n - 2, cache),
        };
        cache.insert(n, result);
        result
    }

    let mut cache = HashMap::new();
    helper(n, &mut cache)
}

/// Memoized Fibonacci using Vec (more efficient for dense range)
pub fn fib_memo_vec(n: usize) -> u64 {
    fn helper(n: usize, cache: &mut Vec<Option<u64>>) -> u64 {
        if let Some(result) = cache[n] {
            return result;
        }
        let result = match n {
            0 => 0,
            1 => 1,
            _ => helper(n - 1, cache) + helper(n - 2, cache),
        };
        cache[n] = Some(result);
        result
    }

    let mut cache = vec![None; n + 1];
    helper(n, &mut cache)
}

// ═══════════════════════════════════════════════════════════════════════════════
// Tabulation (Bottom-Up DP)
// ═══════════════════════════════════════════════════════════════════════════════

/// Tabulated Fibonacci - O(n) time, O(n) space
pub fn fib_tabulation(n: u64) -> u64 {
    if n == 0 {
        return 0;
    }
    if n == 1 {
        return 1;
    }

    let mut table = vec![0u64; (n + 1) as usize];
    table[1] = 1;

    for i in 2..=n as usize {
        table[i] = table[i - 1] + table[i - 2];
    }

    table[n as usize]
}

/// Space-optimized tabulation - O(n) time, O(1) space
pub fn fib_optimized(n: u64) -> u64 {
    if n == 0 {
        return 0;
    }

    let mut a = 0u64;
    let mut b = 1u64;

    for _ in 1..n {
        let temp = a + b;
        a = b;
        b = temp;
    }

    b
}

// ═══════════════════════════════════════════════════════════════════════════════
// Matrix Exponentiation - O(log n)
// ═══════════════════════════════════════════════════════════════════════════════

/// Matrix multiplication for 2x2 matrices
fn matrix_mult(a: [[u64; 2]; 2], b: [[u64; 2]; 2]) -> [[u64; 2]; 2] {
    [
        [
            a[0][0] * b[0][0] + a[0][1] * b[1][0],
            a[0][0] * b[0][1] + a[0][1] * b[1][1],
        ],
        [
            a[1][0] * b[0][0] + a[1][1] * b[1][0],
            a[1][0] * b[0][1] + a[1][1] * b[1][1],
        ],
    ]
}

/// Matrix exponentiation Fibonacci - O(log n)
pub fn fib_matrix(n: u64) -> u64 {
    if n == 0 {
        return 0;
    }

    let mut result = [[1u64, 0], [0, 1]]; // Identity
    let mut base = [[1u64, 1], [1, 0]]; // Fibonacci matrix
    let mut exp = n - 1;

    while exp > 0 {
        if exp % 2 == 1 {
            result = matrix_mult(result, base);
        }
        base = matrix_mult(base, base);
        exp /= 2;
    }

    result[0][0]
}

#[cfg(test)]
mod tests {
    use super::*;

    const EXPECTED: [u64; 21] = [
        0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765,
    ];

    #[test]
    fn test_fib_naive() {
        for (i, &expected) in EXPECTED.iter().enumerate().take(15) {
            assert_eq!(fib_naive(i as u64), expected);
        }
    }

    #[test]
    fn test_fib_memo() {
        for (i, &expected) in EXPECTED.iter().enumerate() {
            assert_eq!(fib_memo(i as u64), expected);
        }
    }

    #[test]
    fn test_fib_memo_vec() {
        for (i, &expected) in EXPECTED.iter().enumerate() {
            assert_eq!(fib_memo_vec(i), expected);
        }
    }

    #[test]
    fn test_fib_tabulation() {
        for (i, &expected) in EXPECTED.iter().enumerate() {
            assert_eq!(fib_tabulation(i as u64), expected);
        }
    }

    #[test]
    fn test_fib_optimized() {
        for (i, &expected) in EXPECTED.iter().enumerate() {
            assert_eq!(fib_optimized(i as u64), expected);
        }
    }

    #[test]
    fn test_fib_matrix() {
        for (i, &expected) in EXPECTED.iter().enumerate() {
            assert_eq!(fib_matrix(i as u64), expected);
        }
    }

    #[test]
    fn test_large_fib() {
        // All methods should agree
        let n = 50;
        let expected = fib_optimized(n);
        assert_eq!(fib_memo(n), expected);
        assert_eq!(fib_tabulation(n), expected);
        assert_eq!(fib_matrix(n), expected);
    }
}

(* Fibonacci: memoisation vs tabulation in OCaml
   OCaml's strength: elegant recursion with memoization via Hashtbl *)

(* 1. Naive recursion — exponential O(2^n) *)
let rec fib_naive n =
  if n <= 1 then n else fib_naive (n-1) + fib_naive (n-2)

(* 2. Top-down memoisation — O(n) time, O(n) space *)
let memo : (int, int) Hashtbl.t = Hashtbl.create 100

let rec fib_memo n =
  if n <= 1 then n
  else match Hashtbl.find_opt memo n with
  | Some v -> v
  | None ->
    let v = fib_memo (n-1) + fib_memo (n-2) in
    Hashtbl.replace memo n v;
    v

(* 3. Bottom-up tabulation — O(n) time, O(n) space *)
let fib_tab n =
  if n <= 1 then n
  else begin
    let t = Array.make (n+1) 0 in
    t.(1) <- 1;
    for i = 2 to n do
      t.(i) <- t.(i-1) + t.(i-2)
    done;
    t.(n)
  end

(* 4. Space-optimised — O(1) space *)
let fib_opt n =
  if n = 0 then 0
  else begin
    let a = ref 0 and b = ref 1 in
    for _ = 2 to n do
      let c = !a + !b in
      a := !b; b := c
    done;
    !b
  end

let () =
  Printf.printf "%-25s" "naive fib(10..20):";
  for i = 10 to 20 do Printf.printf " %d" (fib_naive i) done; print_newline ();
  Printf.printf "%-25s" "memo  fib(50):";
  Printf.printf " %d\n" (fib_memo 50);
  Printf.printf "%-25s" "tab   fib(50):";
  Printf.printf " %d\n" (fib_tab  50);
  Printf.printf "%-25s" "opt   fib(50):";
  Printf.printf " %d\n" (fib_opt  50)

✓ Tests Rust test suite

#[cfg(test)]
mod tests {
    use super::*;

    const EXPECTED: [u64; 21] = [
        0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765,
    ];

    #[test]
    fn test_fib_naive() {
        for (i, &expected) in EXPECTED.iter().enumerate().take(15) {
            assert_eq!(fib_naive(i as u64), expected);
        }
    }

    #[test]
    fn test_fib_memo() {
        for (i, &expected) in EXPECTED.iter().enumerate() {
            assert_eq!(fib_memo(i as u64), expected);
        }
    }

    #[test]
    fn test_fib_memo_vec() {
        for (i, &expected) in EXPECTED.iter().enumerate() {
            assert_eq!(fib_memo_vec(i), expected);
        }
    }

    #[test]
    fn test_fib_tabulation() {
        for (i, &expected) in EXPECTED.iter().enumerate() {
            assert_eq!(fib_tabulation(i as u64), expected);
        }
    }

    #[test]
    fn test_fib_optimized() {
        for (i, &expected) in EXPECTED.iter().enumerate() {
            assert_eq!(fib_optimized(i as u64), expected);
        }
    }

    #[test]
    fn test_fib_matrix() {
        for (i, &expected) in EXPECTED.iter().enumerate() {
            assert_eq!(fib_matrix(i as u64), expected);
        }
    }

    #[test]
    fn test_large_fib() {
        // All methods should agree
        let n = 50;
        let expected = fib_optimized(n);
        assert_eq!(fib_memo(n), expected);
        assert_eq!(fib_tabulation(n), expected);
        assert_eq!(fib_matrix(n), expected);
    }
}

Deep Comparison

OCaml vs Rust: Fibonacci Memoization vs Tabulation

Memoization (Top-Down)

Rust

pub fn fib_memo(n: u64) -> u64 {
    fn helper(n: u64, cache: &mut HashMap<u64, u64>) -> u64 {
        if let Some(&result) = cache.get(&n) {
            return result;
        }
        let result = match n {
            0 => 0, 1 => 1,
            _ => helper(n - 1, cache) + helper(n - 2, cache),
        };
        cache.insert(n, result);
        result
    }
    helper(n, &mut HashMap::new())
}

OCaml

let fib_memo n =
  let cache = Hashtbl.create 100 in
  let rec helper n =
    match Hashtbl.find_opt cache n with
    | Some v -> v
    | None ->
        let result = match n with
          | 0 -> 0 | 1 -> 1
          | _ -> helper (n - 1) + helper (n - 2)
        in
        Hashtbl.add cache n result;
        result
  in
  helper n

Tabulation (Bottom-Up)

Rust

pub fn fib_optimized(n: u64) -> u64 {
    let (mut a, mut b) = (0u64, 1u64);
    for _ in 1..n {
        let temp = a + b;
        a = b;
        b = temp;
    }
    b
}

OCaml

let fib_optimized n =
  let rec loop a b i =
    if i >= n then b
    else loop b (a + b) (i + 1)
  in
  if n = 0 then 0 else loop 0 1 1

Complexity Comparison

Approach	Time	Space
Naive	O(2^n)	O(n) stack
Memoization	O(n)	O(n)
Tabulation	O(n)	O(n)
Optimized	O(n)	O(1)
Matrix	O(log n)	O(1)

Exercises

Implement fib_matrix(n: u64) -> u64 using matrix exponentiation in O(log n) time and O(1) space, and verify it matches the other implementations.

Generalize the memoization pattern: write fn memoize<A: Eq + Hash, B: Clone>(f: impl Fn(A) -> B) -> impl FnMut(A) -> B using a HashMap.

Use the space-optimized form to compute fib(n) mod p for large n and prime p (relevant to competitive programming problems involving Fibonacci modular arithmetic).

Open Source Repos

functional-rust

View the source for this example on GitHub — OCaml and Rust side by side in the repo.

Rust