Lesson 2 · Foundations

Recursion and the Call Stack

Recursion solves a problem by solving smaller instances of the same problem. It relies on the call stack to pause the current function, resolve the subproblem, and resume.

Self-Reference with a Stopping Rule

Recursion is a function defined in terms of itself, applied to a smaller version of its own input. It works because the problem shrinks with each call until it reaches a case simple enough to answer outright.

Every correct recursion has exactly two parts. The base case is the input small enough to answer directly with no further calls — an empty list, a single node, zero. The recursive case reduces the problem and calls itself on the smaller version, then combines the result.

Three conditions must all hold, and a missing one is where recursion fails. There must be at least one base case; every recursive call must make measurable progress toward it; and the base case must actually be reachable from every valid input.

That middle condition is the one most often violated in subtle ways. f(n-1) clearly progresses toward f(0); f(n/2) progresses toward f(1) but never reaches f(0) by integer division from a positive start; and a call like f(n) inside f(n) progresses not at all. Negative inputs frequently break an otherwise-correct base case — factorial(-1) recurses away from zero forever if the base tests n == 0 rather than n <= 0.

Recursion suits problems whose structure is itself recursive. A tree is nodes whose children are trees; a nested list contains lists. Writing an iterative solution over such a structure means managing an explicit stack, which is doing by hand what the language already does — so the recursive version is usually shorter and clearer.

A base case answers directly; a recursive case shrinks and calls itself
Progress must be measurable and the base actually reachable
Guard against inputs that step past the base case, such as negatives
Recursive data structures deserve recursive algorithms

What the Call Stack Costs

Each call allocates a stack frame holding that call's parameters, local variables, and the address to return to. The frame is pushed on entry and popped on return, which is why every level keeps its own independent copy of the locals — the reason recursion works at all.

The consequence is that recursion is not free in memory. A recursion d levels deep holds d frames simultaneously, so space is O(d) even when the function itself allocates nothing. An iterative loop doing the same work uses O(1).

This is the practical limit. The stack is a fixed region — typically 1 to 8 MB — so exceeding it triggers a stack overflow and terminates the program. The depth attainable is a few thousand to a few hundred thousand frames depending on frame size; Python caps it deliberately at 1000 by default and raises RecursionError rather than crashing.

The distinction that matters when analysing space is depth, not call count. Computing Fibonacci naively makes exponentially many calls but is only n frames deep at any moment, because the left branch fully returns before the right one starts. Space is O(n) while time is O(2ⁿ).

For tree algorithms this translates directly: recursion depth is the tree's height. A balanced tree of a million nodes recurses about 20 levels — trivial. A degenerate tree of the same size recurses a million levels and overflows. That gap is why the recursive solution that passes every test can still fail on adversarial input, and why iterative traversals with an explicit stack exist.

A frame per call holds that level's own locals and return address
Space is O(depth), even when the function allocates nothing
Exceeding the stack region raises a stack overflow
Depth is what costs memory, not the total number of calls

The Leap of Faith

The habit that makes recursion tractable is refusing to trace it. Mentally following calls two or three levels deep works for factorial and collapses entirely on a tree — and it is unnecessary.

Instead, assume the recursive call already works on the smaller input, and write only the step that combines its result. To compute the height of a tree: assume the call returns the correct height for each subtree, then the answer is one plus the larger of them. There is no need to imagine how the subtree computed it.

This is induction rather than faith. Verify the base case is correct. Verify that if the recursive calls are correct then the combination is correct. Together those establish correctness for every input, and it is exactly the argument an exam answer should give.

Three questions produce most recursive solutions. What is the smallest input I can answer immediately — that is the base case. How do I make the problem smaller — that is the recursive call. Given the answer to the smaller problem, how do I build mine — that is the combination step.

The combination step is where the algorithm's substance lives, and it is worth noticing that it also decides the traversal order. Combining before recursing gives pre-order; between two calls gives in-order; after gives post-order. Tree traversals are not three separate algorithms, but one recursion with the work placed at three different points.

Assume the recursive call is correct; write only the combining step
It is induction: verify the base, then the inductive step
Ask what is smallest, how it shrinks, and how results combine
Where the work sits relative to the calls decides the traversal order

Key reference

Terms, operations, and practical uses

Core vocabulary

Recursive callA function invoking itself with a modified input.
Base caseThe condition that stops the recursion and returns a concrete value.
Call stackThe internal memory structure that pauses functions and resumes them in LIFO order.

Performance

Stack OverflowA fatal error caused by recursing too deeply and exhausting available memory.
Tail recursionWhen the recursive call is the final action, allowing the compiler to reuse the current stack frame.
MemoizationCaching the results of recursive calls to avoid repeating identical work.

Practical uses

Tree traversalVisiting every node in a branching structure naturally matches recursion's shape.
Divide and conquerSplitting an array in half (like Merge Sort) and recursively sorting both halves.
BacktrackingExploring choices in a maze or combination lock, and returning when a dead-end is found.

Implementation

Calculate factorial recursively

def factorial(n):
    if n <= 1:
        return 1
    return n * factorial(n - 1)
print(factorial(4))

#include <iostream>
using namespace std;
int factorial(int n) {
    if (n <= 1) return 1;
    return n * factorial(n - 1);
}
int main() {
    cout << factorial(4) << '\n';
}

public class Main {
    static int factorial(int n) {
        if (n <= 1) return 1;
        return n * factorial(n - 1);
    }
    public static void main(String[] args) {
        System.out.println(factorial(4));
    }
}

Watch it run

Step through it

Running on n = 4

Output

Read all 9 Steps

Call factorial(4) The initial call checks if n <= 1. It is not, so it must call factorial(3).
Call factorial(3) The computer pauses factorial(4) and pushes factorial(3) onto the stack.
Call factorial(2) factorial(3) pauses and calls factorial(2). The stack grows to size 3.
Call factorial(1) factorial(2) pauses and calls factorial(1).
Hit the base case n <= 1 is now true! factorial(1) returns 1 without recursing.
Resolve factorial(2) factorial(1) pops off, returning 1. factorial(2) resumes and computes 2 * 1 = 2.
Resolve factorial(3) factorial(2) pops off, returning 2. factorial(3) resumes and computes 3 * 2 = 6.
Resolve factorial(4) factorial(3) pops off, returning 6. factorial(4) resumes and computes 4 * 6 = 24.
Return final answer The stack is empty and the final value 24 is returned.

Types of Recursion

Direct recursion calls itself; indirect (or mutual) recursion goes through another function that calls back — the shape of recursive-descent parsers, where parseExpression calls parseTerm which calls back into parseExpression for a parenthesised group.

Linear recursion makes one call per invocation, giving a chain of depth n. Tree recursion makes several, and the call structure branches — which is why naive Fibonacci is exponential while factorial is linear, despite looking similar.

Tail recursion is the case where the recursive call is the very last action, with nothing left to do with its result. That matters because the current frame is no longer needed once the call is made, so a compiler can reuse it instead of pushing a new one — tail call optimisation, which turns the recursion into a loop and makes the space O(1).

The catch is that support is inconsistent. Scheme and other functional languages guarantee it. Most C and C++ compilers perform it at higher optimisation levels. Java, Python, and JavaScript do not — CPython's designer has declined it deliberately, on the grounds that it destroys the stack traces that make debugging possible. So in those languages tail recursion is a stylistic choice with no memory benefit, and deep recursion must be rewritten as a loop by hand.

Recognising overlapping subproblems is the other important classification. When the same subproblem recurs across different branches — as in naive Fibonacci, where fib(n-2) is computed twice — the recursion is doing exponential redundant work, and adding a cache reduces it to linear. That is memoization, and the recursive structure is unchanged by it.

When to prefer iteration: simple linear repetition, performance-critical inner loops, and any input whose depth could exceed the stack. When to prefer recursion: trees, graphs, nested structures, backtracking, and divide-and-conquer — anywhere an iterative version would require you to maintain the stack yourself.

Forms of recursion and what each implies
Form	Shape	Consequence
Linear	One call per invocation	Depth n, O(n) space
Tree	Several calls per invocation	Branching; often exponential time
Tail	The call is the last action	Convertible to a loop — if the language does it
Mutual	Two functions calling each other	Recursive-descent parsers
Overlapping	Same subproblem recurs	Add a cache — this is DP

Linear recurses once; tree recursion branches and can be exponential
Tail recursion is loop-convertible, but Java, Python and JS do not do it
Repeated subproblems mean memoization, not just recursion
Prefer iteration for depth risk, recursion for recursive structures