Recursion Explained: Base Case, Call Stack and Examples

Some problems contain smaller copies of themselves. The factorial of 5 is 5 times the factorial of 4; a folder holds other folders; the string 3[a2[c]] contains 2[c], which must be decoded first. Recursion matches that shape: a function that solves a problem by calling itself on a smaller input, until the input is small enough to answer directly. Trees and graphs are walked with it, backtracking is built on it, and dynamic programming usually starts as a recursive formula.

Why recursion: when loops run out of shape

Nested loops go a fixed number of levels deep. To list every subset of n items you would need n nested loops, one per item — and n is not known until the program runs. Recursion gives each level its own function call, so the depth adapts to the input, as it must for the brackets of Decode String or a tree of unknown height. Every call costs time and memory, though, and using recursion well means knowing when that cost is fine.

The idea: a base case and a recursive case

The factorial says it in two lines: factorial(0) = 1, and factorial(n) = n × factorial(n − 1) for n > 0.

• The base case answers the smallest inputs directly, with no further call.
• The recursive case calls the function on a smaller input and builds its answer from the result.
• Progress: every call moves closer to a base case.

Write the recursive case with a leap of faith: do not trace what factorial(n - 1) does inside. Assume it is right and ask only how to get the factorial of n from it; then check the base case on its own.

Why it works: recursion is induction

The leap of faith is proof by mathematical induction: the base case is right, and if the smaller call is right, one step makes this call right. Correctness climbs one level at a time.

1. To trust a recursive function, check two things. The base case: factorial(0) returns 1, and 0! is 1 — true without any other call.
2. The step, once: assume factorial(0) is right. Then factorial(1) returns 1 × factorial(0) = 1 × 1 = 1, which is 1!. You never trace inside the smaller call — you only use that it is right.
3. The same step again: factorial(1) is right (1), so factorial(2) returns 2 × 1 = 2, which is 2!.
4. The same step again: factorial(2) is right (2), so factorial(3) returns 3 × 2 = 6, which is 3!.
5. The same step again: factorial(3) is right (6), so factorial(4) returns 4 × 6 = 24, which is 4!.
6. The same step again: factorial(4) is right (24), so factorial(5) returns 5 × 24 = 120, which is 5!. Correctness climbs one rung at a time, to every n — this is proof by induction.

The function must also stop: some measure must shrink with every call and be unable to jump past the base case. factorial(-1) counts down past 0 for ever.

The call stack, frame by frame

Each call gets a stack frame holding its parameters, locals and the point to resume at. Frames are pushed on the call stack when a call starts and popped when it returns, so every call keeps its own n.

1. factorial(4) starts: a new frame is pushed with n = 4. It cannot multiply yet — it needs factorial(3) first.
2. factorial(3) is pushed on top. The frames below it are paused mid-line, each waiting for the call above it to return.
3. factorial(2) is pushed on top. The frames below it are paused mid-line, each waiting for the call above it to return.
4. factorial(1) is pushed on top. The frames below it are paused mid-line, each waiting for the call above it to return.
5. factorial(0) is the base case: it answers 1 at once and calls nothing. This is the deepest point — five frames, each holding its own n, all running the same code.
6. factorial(0) returns 1 and its frame is popped. factorial(1) resumes exactly where it paused and does its multiplication: 1 × 1 = 1.
7. factorial(1) returns 1 and its frame is popped. factorial(2) resumes exactly where it paused and does its multiplication: 2 × 1 = 2.
8. factorial(2) returns 2 and its frame is popped. factorial(3) resumes exactly where it paused and does its multiplication: 3 × 2 = 6.
9. factorial(3) returns 6 and its frame is popped. factorial(4) resumes exactly where it paused and does its multiplication: 4 × 6 = 24.
10. factorial(4) returns 24 to main. The work happened on the way back up, and the stack was 5 frames tall at its highest: the memory of a recursion is its depth, O(n) here.

So the memory of a recursion is its depth — O(n) for factorial, though it stores no array — and the work happens on the way back up.

Recursion trees: when one call makes several

A function that makes several calls per call forms a recursion tree, like Fibonacci's fib(n) = fib(n − 1) + fib(n − 2). Time is the number of nodes times the work in each; space is the tree's height, since the stack holds one path from the root at a time.

1. fib(n) = fib(n − 1) + fib(n − 2) makes two calls per call, so the calls form a tree. fib(5) makes 15 calls — and the tree roughly multiplies by 1.6 every time n grows by one.
2. The shaded subtrees recompute values the tree has already found: fib(3) is computed twice and fib(2) three times. 8 of the 15 calls are repeats; fib(30) makes 2,692,537 calls for 31 different values.
3. Memoised, the first fib(k) stores its value and every later call for it returns at once (strong). The repeated subtrees vanish: 9 calls instead of 15, and fib(5) = 5. Linear, not exponential — the first step of dynamic programming.

Naive fib(50) would make about 4 × 10¹⁰ calls for a number a loop finds in 49 additions. Storing each value the first time — memoisation — is the first step of dynamic programming; try it on Fibonacci Number.

Fast exponentiation: xⁿ in O(log n)

Recursion can also make an algorithm faster by shrinking the input by more than one step. xⁿ is (x^(n/2))² when n is even and (x^(n/2))² × x when n is odd, with n/2 rounded down and x⁰ = 1. Each call halves n, so n = 10⁹ needs 31 calls instead of a billion multiplications.

1. power(2, 10) computes 2 to the 10th by halving: with h = power(x, n // 2), the answer is h * h, times one more x when n is odd. The first call cannot finish until power(2, 5) answers, so it waits on the call stack.
2. power(2, 5) is pushed on top and asks for power(2, 2). Each call keeps its own n, so the call below it still remembers where it was; n halves every time, so the stack grows like log n.
3. power(2, 2) is pushed on top and asks for power(2, 1). Each call keeps its own n, so the 2 calls below it still remember where they were; n halves every time, so the stack grows like log n.
4. power(2, 1) is pushed on top and asks for power(2, 0). Each call keeps its own n, so the 3 calls below it still remember where they were; n halves every time, so the stack grows like log n.
5. power(2, 0) hits the base case and returns 1 without calling anything: this is what stops the recursion. The stack is 5 calls deep, its deepest point.
6. power(2, 0) is popped and passes 1 back up. power(2, 1) resumes with h = 1; n = 1 is odd, so it returns 1 * 1 * 2 = 2.
7. power(2, 1) is popped and passes 2 back up. power(2, 2) resumes with h = 2; n = 2 is even, so it returns 2 * 2 = 4.
8. power(2, 2) is popped and passes 4 back up. power(2, 5) resumes with h = 4; n = 5 is odd, so it returns 4 * 4 * 2 = 32.
9. power(2, 5) is popped and passes 32 back up. power(2, 10) resumes with h = 32; n = 10 is even, so it returns 32 * 32 = 1024.
10. power(2, 10) passes 1024 back to its caller and the stack empties. It took 5 calls where a loop would multiply 10 times: O(log n) calls and O(log n) stack space, because n halves on every call.

The line that makes it fast is h = power(x, n / 2) followed by h * h. Writing power(x, n / 2) * power(x, n / 2) looks the same but makes two calls per level.

Merge sort is the same divide and conquer idea with two halves that really are different: about log₂ n levels with n work each, O(n log n) — see sorting algorithms.

The code

The program computes three factorials and three powers, counting the calls power makes. C++ and Java use 64-bit integers, because 13! overflows a 32-bit int.

#include <iostream>
using namespace std;

long long calls = 0; // how many times power() has been entered

// n! for n >= 0.
long long factorial(int n) {
    if (n == 0) return 1;             // base case
    return n * factorial(n - 1);      // recursive case: trust the smaller call
}

// x^n for n >= 0, halving n at every call.
long long power(long long x, int n) {
    calls++;
    if (n == 0) return 1;             // base case
    long long h = power(x, n / 2);    // one call for the half, used twice
    if (n % 2 == 0) return h * h;
    return h * h * x;                 // odd n: one extra factor of x
}

int main() {
    for (int n : {0, 5, 15}) {
        cout << "factorial(" << n << ") = " << factorial(n) << "\n";
    }
    int tests[3][2] = {{2, 10}, {3, 13}, {2, 30}};
    for (auto& t : tests) {
        calls = 0;
        long long result = power(t[0], t[1]);
        cout << "power(" << t[0] << ", " << t[1] << ") = " << result << " in " << calls << " calls\n";
    }
    return 0;
}

public class Main {
    static long calls = 0; // how many times power() has been entered

    // n! for n >= 0.
    static long factorial(int n) {
        if (n == 0) return 1;             // base case
        return n * factorial(n - 1);      // recursive case: trust the smaller call
    }

    // x^n for n >= 0, halving n at every call.
    static long power(long x, int n) {
        calls++;
        if (n == 0) return 1;             // base case
        long h = power(x, n / 2);         // one call for the half, used twice
        if (n % 2 == 0) return h * h;
        return h * h * x;                 // odd n: one extra factor of x
    }

    public static void main(String[] args) {
        for (int n : new int[] {0, 5, 15}) {
            System.out.println("factorial(" + n + ") = " + factorial(n));
        }
        int[][] tests = {{2, 10}, {3, 13}, {2, 30}};
        for (int[] t : tests) {
            calls = 0;
            long result = power(t[0], t[1]);
            System.out.println("power(" + t[0] + ", " + t[1] + ") = " + result + " in " + calls + " calls");
        }
    }
}

calls = 0  # how many times power() has been entered


def factorial(n):
    """n! for n >= 0."""
    if n == 0:
        return 1                      # base case
    return n * factorial(n - 1)       # recursive case: trust the smaller call


def power(x, n):
    """x^n for n >= 0, halving n at every call."""
    global calls
    calls += 1
    if n == 0:
        return 1                      # base case
    h = power(x, n // 2)              # one call for the half, used twice
    if n % 2 == 0:
        return h * h
    return h * h * x                  # odd n: one extra factor of x


for n in (0, 5, 15):
    print(f"factorial({n}) = {factorial(n)}")
for x, n in ((2, 10), (3, 13), (2, 30)):
    calls = 0
    result = power(x, n)
    print(f"power({x}, {n}) = {result} in {calls} calls")

let calls = 0; // how many times power() has been entered

// n! for n >= 0.
function factorial(n) {
  if (n === 0) return 1; // base case
  return n * factorial(n - 1); // recursive case: trust the smaller call
}

// x^n for n >= 0, halving n at every call.
function power(x, n) {
  calls++;
  if (n === 0) return 1; // base case
  const h = power(x, Math.floor(n / 2)); // one call for the half, used twice
  if (n % 2 === 0) return h * h;
  return h * h * x; // odd n: one extra factor of x
}

for (const n of [0, 5, 15]) {
  console.log(`factorial(${n}) = ${factorial(n)}`);
}
for (const [x, n] of [[2, 10], [3, 13], [2, 30]]) {
  calls = 0;
  const result = power(x, n);
  console.log(`power(${x}, ${n}) = ${result} in ${calls} calls`);
}

factorial(0) = 1
factorial(5) = 120
factorial(15) = 1307674368000
power(2, 10) = 1024 in 5 calls
power(3, 13) = 1594323 in 5 calls
power(2, 30) = 1073741824 in 6 calls

Count Good Numbers raises powers near 10⁹ modulo 10⁹ + 7, taking the remainder after every multiplication.

Recursion on arrays and strings

An array is its first element followed by a smaller array: sum(arr, i) is arr[i] + sum(arr, i + 1). A string is its two ends around a shorter string: reversing swaps the ends and recurses on lo + 1, hi − 1. Pass indices, never slices — arr[1:] copies the rest at every call, O(n²) work for an O(n) task. These go n or n/2 calls deep, which matters below; Reverse String is the two pointers technique written this way.

From recursion to backtracking: every subset

Back to the problem loops could not solve: each call decides about one element, out or in, and when nothing is left to decide, the choices on the way down form one subset.

1. Each level decides one element: the dashed edge leaves it out, the solid edge puts it in. 3 elements, 3 levels, and 2 to the power 3 = 8 leaves — one per subset. No fixed number of loops could do this for any n.
2. The first call goes down the "out" edges to a leaf: every element decided, nothing chosen, so it prints []. The stack is 4 calls deep — O(n) space.
3. Back up 1 level (each return undoes its choice with a pop), then down the other edge: [3] is printed.
4. Back up 2 levels, then down the other edge: [2] is printed.
5. Back up 1 level, then down the other edge: [2, 3] is printed.
6. Back up 3 levels, then down the other edge: [1] is printed.
7. Back up 1 level, then down the other edge: [1, 3] is printed.
8. Back up 2 levels, then down the other edge: [1, 2] is printed.
9. Back up 1 level, then down the other edge: [1, 2, 3] is printed. All 8 subsets, each exactly once: O(n × 2ⁿ) time.

The code

One current list holds the subset being built: a push before the call and a pop after it leave current exactly as it was for the next branch.

#include <iostream>
#include <vector>
using namespace std;

// Prints every subset of nums[i..] after the elements already in current.
// Returns how many subsets it printed.
int subsets(const vector<int>& nums, int i, vector<int>& current) {
    if (i == (int)nums.size()) {               // base case: every element decided
        cout << "[";
        for (size_t k = 0; k < current.size(); k++) cout << (k ? ", " : "") << current[k];
        cout << "]\n";
        return 1;
    }
    int found = subsets(nums, i + 1, current); // leave nums[i] out
    current.push_back(nums[i]);                // put nums[i] in ...
    found += subsets(nums, i + 1, current);
    current.pop_back();                        // ... and take it back out
    return found;
}

int main() {
    vector<int> nums = {1, 2, 3};
    vector<int> current;
    int total = subsets(nums, 0, current);
    cout << total << " subsets\n";
    return 0;
}

import java.util.ArrayList;
import java.util.List;

public class Main {
    // Prints every subset of nums[i..] after the elements already in current.
    // Returns how many subsets it printed.
    static int subsets(int[] nums, int i, List<Integer> current) {
        if (i == nums.length) {                    // base case: every element decided
            System.out.println(current);
            return 1;
        }
        int found = subsets(nums, i + 1, current); // leave nums[i] out
        current.add(nums[i]);                      // put nums[i] in ...
        found += subsets(nums, i + 1, current);
        current.remove(current.size() - 1);        // ... and take it back out
        return found;
    }

    public static void main(String[] args) {
        int[] nums = {1, 2, 3};
        int total = subsets(nums, 0, new ArrayList<>());
        System.out.println(total + " subsets");
    }
}

def subsets(nums, i, current):
    """Print every subset of nums[i:] after the elements already in current.
    Return how many subsets were printed."""
    if i == len(nums):                       # base case: every element decided
        print(current)
        return 1
    found = subsets(nums, i + 1, current)    # leave nums[i] out
    current.append(nums[i])                  # put nums[i] in ...
    found += subsets(nums, i + 1, current)
    current.pop()                            # ... and take it back out
    return found


nums = [1, 2, 3]
total = subsets(nums, 0, [])
print(f"{total} subsets")

// Prints every subset of nums[i..] after the elements already in current.
// Returns how many subsets it printed.
function subsets(nums, i, current) {
  if (i === nums.length) {
    // base case: every element decided
    console.log(`[${current.join(", ")}]`);
    return 1;
  }
  let found = subsets(nums, i + 1, current); // leave nums[i] out
  current.push(nums[i]); // put nums[i] in ...
  found += subsets(nums, i + 1, current);
  current.pop(); // ... and take it back out
  return found;
}

const nums = [1, 2, 3];
const total = subsets(nums, 0, []);
console.log(`${total} subsets`);

[]
[3]
[2]
[2, 3]
[1]
[1, 3]
[1, 2]
[1, 2, 3]
8 subsets

The push, the call and the pop are choose, explore, unchoose. Add a rule that refuses some choices and the same skeleton becomes backtracking; Subsets asks for exactly this list.

How deep can recursion go?

Every waiting call holds a frame, and the call stack is small:

Depth O(log n) — fast power, a balanced tree — is always safe. Depth O(n) — a linked list, a tree that may be one long path — fails once n reaches thousands. Then convert: a call with nothing left to do after its recursive call is a loop in disguise, and one that must come back uses a loop with an explicit stack, as in depth-first search. Tail calls do not save you here: a compiler may reuse the frame when the call is the last thing a function does, but Python, Java and Node never do.

Time and space complexity

The last row cannot be beaten: an answer with 2ⁿ entries takes at least that long to list.

How to recognise a recursive problem

• The definition refers to itself: a tree from its subtrees, 3[a2[c]] from 2[c].
• The input is nested to an unknown depth.
• The answer for n follows from a smaller case, as in Find the Winner of the Circular Game.
• You must generate every subset, arrangement or path.

Common mistakes

• A missing or unreachable base case: fib with only if n == 0 calls fib(−1).
• Dropping the recursive result: you get None or undefined further up.
• Calling twice what you could call once: O(log n) becomes O(n).
• Copying the input at every call: pass indices.
• Overflow: 13! overflows a 32-bit int.
• Not undoing shared state: forget the pop and later subsets inherit stale elements.

Practice in this order

1. Fibonacci Number: two base cases, then memoise.
2. Power of Three: divide until a base case answers.
3. Reverse String: two indices, one call at a time.
4. Count Good Numbers: fast power with a modulus.
5. Find the Winner of the Circular Game: from n − 1 players to n.
6. Find Kth Bit in Nth Binary String: recurse into one half.
7. Decode String: one call per level of nesting.
8. Different Ways to Add Parentheses: divide and conquer at every operator.

The recursion problem list has every problem in the catalogue that practises it. When the first five feel natural, move on to backtracking, which turns the subsets recursion into a general way of searching.