Part 2 · 1 chapters · ~8 min

Induction and Recursion

Mathematical induction and strong induction, recursive definitions (lists, trees, natural numbers), proving recursive functions correct, structural induction over trees and JSON, termination arguments, recursion versus iteration, tail calls, and memoisation.

Proving recursion correct

code

// claim: sum(n) = n(n+1)/2 for all n ≥ 0
const sum = (n: number): number => n === 0 ? 0 : n + sum(n - 1);
// base: sum(0) = 0 = 0·1/2 ✓
// step: assume sum(k) = k(k+1)/2. Then sum(k+1) = (k+1) + k(k+1)/2 = (k+1)(k+2)/2 ✓

// structural induction: a function over JSON is correct if it handles each shape,
// assuming it is correct on the (smaller) children
type Json = null | boolean | number | string | Json[] | { [k: string]: Json };
const depth = (j: Json): number =>
  Array.isArray(j) ? 1 + Math.max(0, ...j.map(depth))
  : j !== null && typeof j === 'object' ? 1 + Math.max(0, ...Object.values(j).map(depth))
  : 0;

Termination needs a measure that strictly decreases and is bounded below (n, the length of a list, the size of a tree). Recursion whose input does not shrink (a cycle in a graph) loops forever, which is why graph traversals keep a visited set (part 5).

INDUCTION AND RECURSION ARE THE SAME SHAPE

prove the base, prove the step, get every n

swipe the figure sideways, or tap expand for full screen

1/4

base

Prove the statement for the smallest case. In code: the base case of the recursion returns a correct answer directly.

smallest case, directlythe recursion's base case