Recursion and Dynamic Programming

DP

Fibonacci with Memoization

Compute fib(n) by building the memo table from fib(0) and fib(1) upward. Each new entry is the sum of the two immediately preceding entries; the table itself replaces the redundant recursive calls.

Algorithm

Canonical input n = 6 finishes after six reductions; the printed result is 8.

memo table The recursive CTE materializes a `(n, fib(n))` row for every step visited, so each entry is computed exactly once.
rolling pair A two-column carry `(fn, fn_minus_1)` is enough state to advance the sequence one position; the full memo can still be inspected by querying the CTE rows directly.

Basic Implementation

basic.sql
Replay: real traced execution (multi-file project)
.mode list
.headers off
WITH RECURSIVE fib(n, fn, fn_minus_1) AS (
  SELECT 0, 0, 1
  UNION ALL
  SELECT n + 1, fn + fn_minus_1, fn
  FROM fib
  WHERE n < 6
)
SELECT fn FROM fib WHERE n = 6;

  1. n ← 0, fn ← 0, fn_minus_1 ← 1

    1.mode list2.headers off
    values this step0n0fn1fn_minus_1

  2. n ← 1, fn ← 1, fn_minus_1 ← 0

    1.mode list2.headers off
    values this step0 → 1n0 → 1fn1 → 0fn_minus_1

  3. n ← 2, fn_minus_1 ← 1

    1.mode list2.headers off
    values this step1 → 2n0 → 1fn_minus_11fn

  4. n ← 3, fn ← 2

    1.mode list2.headers off
    values this step2 → 3n1 → 2fn1fn_minus_1

  5. n ← 4, fn ← 3, fn_minus_1 ← 2

    1.mode list2.headers off
    values this step3 → 4n2 → 3fn1 → 2fn_minus_1

  6. n ← 5, fn ← 5, fn_minus_1 ← 3

    1.mode list2.headers off
    values this step4 → 5n3 → 5fn2 → 3fn_minus_1

  7. n ← 6, fn ← 8, fn_minus_1 ← 5

    1.mode list2.headers off
    values this step5 → 6n5 → 8fn3 → 5fn_minus_1

  8. stdout ← 8

    1.mode list2.headers off
    values this step8stdout8fn

Complexity

  • Time: O(n)
  • Space: O(n) for the materialized CTE rows

Implementation notes

  • SQL: SQLite cannot consult a recursive CTE non-linearly, so a two-call lookup fib(n - 1) + fib(n - 2) does not translate directly. The lesson uses the dual-carry rolling memo: each row carries (n, fib(n), fib(n - 1)), and the recursive arm advances (n + 1, fib(n) + fib(n - 1), fib(n)). The memo table is the materialized CTE itself; every (n, fn) pair is computed exactly once.
  • The base row (0, 0, 1) encodes fib(0) = 0 with fib(-1) = 1 as the seed of the rolling pair so the first recursive step lands on fib(1) = 0 + 1 = 1.
  • The final SELECT fn FROM fib WHERE n = 6 reads the cached entry out of the memo. Replacing 6 with any n < 93 would still return the right value before SQLite's INTEGER overflow kicks in.