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.

Basic Implementation

basic.sql 
.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;

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.
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.