Recursion — theory and understanding

Build the intuition for recursion — a function that calls itself on a smaller subproblem, the role of the base case, the call stack, and the 'recursive faith' mental model that makes recursive code easy to write.

What is recursion?

Recursion is when a function calls itself on a smaller version of the same problem, until it hits a case so small it can be answered directly.

A contest-worthy intuition: the function is defined in terms of itself, the way you define factorial:

Example

0! = 1 (base case)

n! = n × (n - 1)! (recursive case)

The definition refers to itself, but only on a smaller input. As long as every recursive call brings us closer to a base case, the process eventually stops.

Why bother? Many problems are naturally recursive — trees, divide-and-conquer (binary search, merge sort), backtracking (subsets, permutations, N-Queens), and most DP problems are easiest to write recursively first, then optimize.

Every recursive function has two parts

Every correct recursive function answers two questions:

Base case — what is the answer when the input is small enough to solve directly? (No recursive call needed.)
Recursive case — assuming the function works on smaller inputs, how do we build the answer for the current input?

Missing either one leads to bugs:

No base case → infinite recursion → stack overflow.
Wrong recursive case → wrong answer, possibly silent.

Template:

ReturnType solve(args) {
    if (base case)           // 1. handle the smallest input
        return base answer;
    return combine(solve(smaller args));   // 2. recurse on smaller and combine
}

Example — factorial:

long long fact(int n) {
    if (n == 0) return 1;               // base case
    return n * fact(n - 1);             // recursive case
}

Example — sum of array a[0..n-1]:

long long sumArr(const vector<int>& a, int n) {
    if (n == 0) return 0;               // base: empty prefix
    return a[n - 1] + sumArr(a, n - 1); // recurse on prefix of size n-1
}

The mental model — recursive faith

The single most useful trick for writing recursive code is recursive faith (a.k.a. the leap of faith).

Assume the recursive call already works on smaller inputs. Now write the one step that handles the current input using that assumption.

Do not trace the recursion in your head — that way lies madness for anything non-trivial. Instead:

Identify the smaller subproblem the function should solve.
Assume the recursive call returns the right answer for it.
Combine that answer with one step of work to handle the current input.
Handle the base case so the assumption can eventually pay off.

That is the entire art. Once you trust the call, recursive code becomes natural to write.

Example — reverse a string of length n:

Example

If I trust that reverse(s, 1, n - 1) reverses the inside,

then reverse(s, 0, n - 1) = swap s[0] with s[n - 1], then reverse the inside.

void reverse(string& s, int l, int r) {
    if (l >= r) return;             // base: 0 or 1 characters
    swap(s[l], s[r]);
    reverse(s, l + 1, r - 1);       // trust this reverses the middle
}

How the call stack works

Each function call gets its own stack frame — a chunk of memory holding the function's parameters, local variables, and where to return. When a function calls itself, a new frame is pushed on top. When a call returns, its frame is popped.

Trace of fact(4):

Example

fact(4) push frame for n=4

→ calls fact(3) push frame for n=3

→ calls fact(2) push frame for n=2

→ calls fact(1) push frame for n=1

→ calls fact(0) push frame for n=0

→ returns 1 pop frame, return value 1

→ returns 1 * 1 = 1 pop, return 1

→ returns 2 * 1 = 2 pop, return 2

→ returns 3 * 2 = 6 pop, return 6

→ returns 4 * 6 = 24 pop, return 24

Visualization of the call stack at maximum depth (just before fact(0) returns):

Example

┌──────────────┐ ← top of stack

│ fact(n=0) │

├──────────────┤

│ fact(n=1) │

├──────────────┤

│ fact(n=2) │

├──────────────┤

│ fact(n=3) │

├──────────────┤

│ fact(n=4) │

└──────────────┘ ← bottom of stack

Why this matters for contests:

Depth = stack memory. Default stack size on most judges is around 1 MB; recursing ~10⁵–10⁶ times can crash. Trees and lists with n = 10⁶ can overflow if you naïvely recurse.
Each frame stores local variables — passing big objects by value duplicates them at every level.
Recursion is slower than iteration by a constant factor (frame setup), but rarely the bottleneck in contest problems.

Recursion trees — visualizing the work

When a function makes multiple recursive calls, drawing the recursion tree is the fastest way to estimate complexity.

Example — fib(5):

Example

fib(5)

/ \

fib(4) fib(3)

/ \ / \

fib(3) fib(2) fib(2) fib(1)

/ \ / \ / \

fib(2) fib(1) fib(1) fib(0) fib(1) fib(0)

/ \

fib(1) fib(0)

Number of nodes ≈ O(2ⁿ) — that exponential blow-up is why naïve Fibonacci is slow, and why memoization turns it into O(n).

Three quick complexity intuitions from the tree:

Linear recursion (one call per level): depth = n → O(n) time, O(n) stack.
Binary recursion (two calls per level): up to 2ⁿ leaves → O(2ⁿ) unless cached.
Divide-and-conquer (two calls on half the size): depth log n, work doubles per level → O(n log n) typical (e.g. merge sort).

When is recursion the right tool?

Recursion is strictly equivalent to iteration in expressive power — anything you can do with one, you can do with the other. The choice is about clarity and fit.

Use recursion when:

The problem is naturally recursive — trees, expression evaluation, divide-and-conquer.
You need to explore branching choices — subsets, permutations, backtracking, search.
A DP problem is easier to write top-down with memoization than bottom-up.

Prefer iteration when:

The problem is naturally linear and shallow (summing, transforming).
The recursion depth could overflow the stack (huge inputs).
You need maximum speed in a tight loop (rare in contest problems, but possible).

Rule of thumb in contests: write the recursive version first because it is easier to think about. Convert to iteration only if depth or speed forces it.

What is recursion?

Recursion is when a function calls itself on a smaller version of the same problem, until it hits a case so small it can be answered directly.

A contest-worthy intuition: the function is defined in terms of itself, the way you define factorial:

Example

0! = 1 (base case)

n! = n × (n - 1)! (recursive case)

The definition refers to itself, but only on a smaller input. As long as every recursive call brings us closer to a base case, the process eventually stops.

Every recursive function has two parts

Every correct recursive function answers two questions:

Base case — what is the answer when the input is small enough to solve directly? (No recursive call needed.)
Recursive case — assuming the function works on smaller inputs, how do we build the answer for the current input?

Missing either one leads to bugs:

No base case → infinite recursion → stack overflow.
Wrong recursive case → wrong answer, possibly silent.

Template:

ReturnType solve(args) {
    if (base case)           // 1. handle the smallest input
        return base answer;
    return combine(solve(smaller args));   // 2. recurse on smaller and combine
}

Example — factorial:

long long fact(int n) {
    if (n == 0) return 1;               // base case
    return n * fact(n - 1);             // recursive case
}

Example — sum of array a[0..n-1]:

long long sumArr(const vector<int>& a, int n) {
    if (n == 0) return 0;               // base: empty prefix
    return a[n - 1] + sumArr(a, n - 1); // recurse on prefix of size n-1
}

The mental model — recursive faith

The single most useful trick for writing recursive code is recursive faith (a.k.a. the leap of faith).

Assume the recursive call already works on smaller inputs. Now write the one step that handles the current input using that assumption.

Do not trace the recursion in your head — that way lies madness for anything non-trivial. Instead:

Identify the smaller subproblem the function should solve.
Assume the recursive call returns the right answer for it.
Combine that answer with one step of work to handle the current input.
Handle the base case so the assumption can eventually pay off.

That is the entire art. Once you trust the call, recursive code becomes natural to write.

Example — reverse a string of length n:

Example

If I trust that reverse(s, 1, n - 1) reverses the inside,

then reverse(s, 0, n - 1) = swap s[0] with s[n - 1], then reverse the inside.

void reverse(string& s, int l, int r) {
    if (l >= r) return;             // base: 0 or 1 characters
    swap(s[l], s[r]);
    reverse(s, l + 1, r - 1);       // trust this reverses the middle
}

How the call stack works

Trace of fact(4):

Example

fact(4) push frame for n=4

→ calls fact(3) push frame for n=3

→ calls fact(2) push frame for n=2

→ calls fact(1) push frame for n=1

→ calls fact(0) push frame for n=0

→ returns 1 pop frame, return value 1

→ returns 1 * 1 = 1 pop, return 1

→ returns 2 * 1 = 2 pop, return 2

→ returns 3 * 2 = 6 pop, return 6

→ returns 4 * 6 = 24 pop, return 24

Visualization of the call stack at maximum depth (just before fact(0) returns):

Example

┌──────────────┐ ← top of stack

│ fact(n=0) │

├──────────────┤

│ fact(n=1) │

├──────────────┤

│ fact(n=2) │

├──────────────┤

│ fact(n=3) │

├──────────────┤

│ fact(n=4) │

└──────────────┘ ← bottom of stack

Why this matters for contests:

Depth = stack memory. Default stack size on most judges is around 1 MB; recursing ~10⁵–10⁶ times can crash. Trees and lists with n = 10⁶ can overflow if you naïvely recurse.
Each frame stores local variables — passing big objects by value duplicates them at every level.
Recursion is slower than iteration by a constant factor (frame setup), but rarely the bottleneck in contest problems.

Recursion trees — visualizing the work

When a function makes multiple recursive calls, drawing the recursion tree is the fastest way to estimate complexity.

Example — fib(5):

Example

fib(5)

/ \

fib(4) fib(3)

/ \ / \

fib(3) fib(2) fib(2) fib(1)

/ \ / \ / \

fib(2) fib(1) fib(1) fib(0) fib(1) fib(0)

/ \

fib(1) fib(0)

Number of nodes ≈ O(2ⁿ) — that exponential blow-up is why naïve Fibonacci is slow, and why memoization turns it into O(n).

Three quick complexity intuitions from the tree:

Linear recursion (one call per level): depth = n → O(n) time, O(n) stack.
Binary recursion (two calls per level): up to 2ⁿ leaves → O(2ⁿ) unless cached.
Divide-and-conquer (two calls on half the size): depth log n, work doubles per level → O(n log n) typical (e.g. merge sort).

When is recursion the right tool?

Recursion is strictly equivalent to iteration in expressive power — anything you can do with one, you can do with the other. The choice is about clarity and fit.

Use recursion when:

The problem is naturally recursive — trees, expression evaluation, divide-and-conquer.
You need to explore branching choices — subsets, permutations, backtracking, search.
A DP problem is easier to write top-down with memoization than bottom-up.

Prefer iteration when:

The problem is naturally linear and shallow (summing, transforming).
The recursion depth could overflow the stack (huge inputs).
You need maximum speed in a tight loop (rare in contest problems, but possible).

Rule of thumb in contests: write the recursive version first because it is easier to think about. Convert to iteration only if depth or speed forces it.