Recursion
The problem
Some problems are most naturally described in terms of smaller versions of themselves (traversing a tree, computing a factorial) — recursion lets a function solve a problem by calling itself on a smaller input, avoiding the need to manually manage a stack of pending work.
Why now
Functions and scope gives us the ability to call a function, but nothing yet says a function can call itself. Proof techniques already introduced induction — prove the base case, prove the step — and recursion is that exact argument turned into an executable program: the base case stops the calls, the inductive step is the self-call.
Mental model
A recursive function trusts itself: it assumes the recursive call correctly solves the smaller subproblem, and only has to handle combining that answer with the current step. This is induction, executed — if you can trust the induction step, you can trust the recursive call.
Requires
- Functions & ScopeProgramming Fundamentals
Recursion is a function calling itself; without the function/call/scope machinery a self-call has no mechanism (no call stack frame, no local state per call) to work with.
- Proof TechniquesMathematical Thinking
Recursion's correctness argument is literally induction — trusting the recursive call on a smaller input is the inductive hypothesis, and the base case is the induction's base case.
Helps
- Recurrence RelationsMathematical Thinking
Analyzing how much work a recursive function does requires writing and solving its recurrence relation; useful once you're past writing correct recursive functions and into reasoning about their cost.
Unlocks
Related
Used in
- Tree and graph traversal (DOM traversal, file system walks, JSON parsing)
- Divide-and-conquer algorithms (merge sort, quicksort)
- Recursive descent parsers in compilers and interpreters
- React's component tree rendering (components rendering child components)
Projects
- Implement a recursive function to sum a nested array of arbitrary depth, then convert it to an iterative version using an explicit stack
- Write a recursive directory-listing function and trace its call stack by hand for a 3-level-deep folder
Examples
- factorial(n) = n <= 1 ? 1 : n * factorial(n - 1) — base case n<=1, inductive step trusts factorial(n-1)
- A DOM tree walker that calls itself on every child node is recursion mirroring the tree's own recursive structure
Resources
Mastery checklist
- I can identify the base case and recursive case in any recursive function
- I can explain recursion's correctness in terms of induction
- I can convert a simple recursive function into an equivalent iterative one
- I can trace a recursive call stack by hand and predict stack depth