Recursion and Dynamic Programming

Recursion

Factorial

Compute n! using a recursive definition: 0! = 1, otherwise n! = n * (n - 1)!. The classic introduction to a self-referential function.

Algorithm

Basic Implementation

basic.sql 
.mode list
.headers off
WITH RECURSIVE factorial(n, result) AS (
  SELECT 0, 1
  UNION ALL
  SELECT n + 1, result * (n + 1)
  FROM factorial
  WHERE n < 5
)
SELECT result FROM factorial WHERE n = 5;

The pinned run is factorial(5). The diagrams separate the descent, the base case, and the return values so the stack does not feel invisible.

Step 1 - Descend to the base case

Each call waits for one smaller call until f(0) returns 1.

Call tree for factorial(5): f(5) waits on f(4), down to f(0).f(5)waitsf(4)waitsf(3)waitsf(2)waitsf(1)waitsf(0)base = 1

Step 2 - Base value starts the unwind

The first finished frame is f(0) = 1; f(1) can now compute 1 * 1.

Call stack just before unwind begins.top -> bottomknown returnf(0)1f(1)waitingf(2)waitingf(3)waitingf(4)waitingf(5)waiting

Step 3 - Unwind returns 120

Each frame multiplies its n by the completed smaller result.

Return chain for factorial(5).framecalculationreturnsf(0)base1f(1)1 * 11f(2)2 * 12f(3)3 * 26f(4)4 * 624f(5)5 * 24120

Complexity

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

Implementation notes

  • SQL: SQLite has no procedural RETURN value, so the recursive definition is unrolled in a WITH RECURSIVE factorial(n, result) CTE. The seed row (0, 1) is the base case; each recursive arm multiplies result by n + 1 and writes the next row. The WHERE n < 5 guard mirrors the imperative loop bound.
  • The final projection SELECT result FROM factorial WHERE n = 5 picks the row produced after the last multiplication. Replacing 5 with another input would reproduce n! for that value.
  • A direct SELECT exp(SUM(log(...))) would feel clever but lose the educational recursion the lesson is teaching; the explicit CTE keeps each multiplication step visible.
base case `0! = 1` ends the recursion.
recursive case `n! = n * (n - 1)!` reduces the input each step until the base case fires.