Lesson 06 of 16 · 19:02
Recursion
Recursion works when a function can solve one piece of a problem and delegate a strictly smaller version of the same problem. The key is a contract: a precise sentence describing what a call returns. Once that contract is clear, the recursive call can be trusted like any other helper function.
The call stack is real memory. Calls accumulate while descending toward a base case, then finish in reverse order while unwinding. Where work appears relative to the recursive call determines traversal order and often the meaning of the algorithm.
What you should be able to do after this lesson
- Write the return contract first
- Prove progress toward a base case
- Separate total calls from maximum active depth
The mental model
Each call owns one frame and waits for the smaller call to return a promised fact. The stack grows on the way down and combines results on the way back up.
Recognize it when: Recursion fits naturally when the input is recursive—trees, lists, divide-and-conquer ranges, or a decision tree—and each step can make measurable progress toward a base case.
The invariant to say aloud: Every call receives a strictly smaller or closer-to-base state and returns exactly the fact described by the function contract.
Learn the ideas one at a time
Concept 1 of 5
Base case
Watch from 0:00 ↗The smallest valid input returns directly. Without it, or without progress toward it, recursion does not terminate.
The base case answers the smallest valid state directly and anchors the proof. Progress is equally important: every recursive edge must move closer to that state. A base case that exists but can never be reached does not prevent infinite recursion.
Walk through an example
For length(node), null returns 0. A real node returns 1 + length(node.next). Following next shortens the remaining suffix, so the null base case must eventually be reached in an acyclic list.
In an interview
Test the base case mentally before the general case. Empty inputs often reveal whether the function's promised return value is actually coherent.
Concept 2 of 5
Call stack
Watch from 4:07 ↗Each active call stores parameters, locals, and a return point. Maximum simultaneous depth—not total call count—determines stack space.
Each active call stores parameters, local variables, and where execution should resume. Total calls determine time; the longest chain of calls alive at once determines stack space. Branching recursion can make many calls without keeping all of them active simultaneously.
Walk through an example
f(3) waits for f(2), which waits for f(1), which waits for f(0). Four frames are alive at the deepest point; returning f(0) releases frames one by one.
In an interview
Give stack complexity in terms of recursion depth h, then translate h for the input shape: log n for a balanced tree and n for a chain.
Concept 3 of 5
Execution order
Watch from 9:55 ↗Code before the recursive call executes while descending; code after it executes while unwinding. That distinction creates preorder versus postorder behavior.
Statements before a recursive call run on descent; statements after it run on unwind. In a tree, processing before both child calls is preorder, between them is inorder, and after them is postorder. The code position directly expresses when a node is considered complete.
Walk through an example
For root with children L and R: print before calls gives root, L, R. Print between calls gives L, root, R. Print after calls gives L, R, root.
In an interview
Choose the order from the information dependency: use postorder when a parent needs completed results from its children.
Concept 4 of 5
Complexity
Watch from 11:16 ↗Count calls and work per call for time; count maximum depth for auxiliary space. A linear chain can be O(n) time and O(n) stack.
Count the number of distinct calls and multiply by non-recursive work per call. Beware of slicing, string concatenation, or repeated scans inside each call. Space is the maximum stack depth plus any structures retained across calls, not the total number of frames ever created.
Walk through an example
A recursive list walk visits n nodes once, so time is O(n), and the chain keeps n frames, so space is O(n). A divide-and-conquer recurrence can have O(n) total calls but only O(log n) depth.
In an interview
Draw the recursion tree when branching makes the call count unclear, and separately mark the longest root-to-leaf path for space.
Concept 5 of 5
Linked-list example
Watch from 13:52 ↗A node points to a smaller suffix, so recursion can process one node and delegate the remainder. The return value must state what is known about that suffix.
A list node naturally owns a smaller list beginning at next. Define the child contract precisely—for example, reverse(node) returns the head of the reversed suffix—then use that returned head while rewiring the current edge on unwind.
Walk through an example
To reverse A → B → C, the call on B returns C → B. Set B.next = A and A.next = null, then return the same head C. Each frame appends its node to the reversed suffix.
In an interview
Name what the recursive call has already completed. If you cannot say that in one sentence, pause before coding.
Before you call this lesson done
- State the contract
- Handle the smallest valid state
- Show strict progress
- Count calls and maximum depth separately
