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

Canonical input n = 5 finishes after five reductions; the printed result is 120.

base case `0! = 1` ends the recursion.
recursive case `n! = n * (n - 1)!` reduces the input each step until the base case fires.

Visual walkthrough

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

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;

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.