Introduction to Recursion

Definition

Recursion is when a function calls itself — directly or through a chain of other functions — to solve a problem by breaking it into a smaller version of the same problem.

The skeleton looks like this:

void func() {
    // Some work
    func();   // call myself with a smaller version of the problem
    // Some work
}

That’s the entire idea. What makes it work (and not loop forever) is the base case.

The three rules

Every correct recursive function obeys all three:

1. The function calls itself. (Otherwise it isn’t recursion.)
2. There is a base case — at least one input where the function returns without recursing.
3. Each recursive call moves toward the base case. The argument shrinks, the range narrows, the tree gets smaller. Otherwise we recurse forever.

Miss any one of these and you get a stack overflow — the call stack grows until your program crashes.

// Counts down from N to 1, then stops.
void count(int N) {
    if (N == 0) return;        //  ← base case
    cout << N << " ";
    count(N - 1);              //  ← progress toward base case
}

Worked example: Factorial

Factorial of N is N · (N-1) · (N-2) · … · 1. The recursive definition is one line:

factorial(0) = 1
factorial(N) = N * factorial(N - 1)

The base case (N == 0) and the recursive case fall straight out of the math.

int factorial(int N) {
    if (N == 0) return 1;          // base case
    return N * factorial(N - 1);   // recursive case
}

def factorial(N):
    if N == 0:
        return 1
    return N * factorial(N - 1)

int factorial(int N) {
    if (N == 0) return 1;
    return N * factorial(N - 1);
}

The recursion tree

factorial(5) produces a single chain of calls — one call per level. There’s no branching because each call makes exactly one recursive call.

The green box is the base case. Each box shows what it eventually returned.

How the call stack does the bookkeeping

Every call to factorial(N) pushes a stack frame containing its local N. The frame waits — paused — until the recursive call returns. Then it multiplies and returns.

Notice the rhythm: push down, hit the base, then pop back up multiplying along the way. That’s the call stack doing your work for you.

Stack overflow — the danger

The call stack has a fixed maximum depth (a few thousand in most environments). Two things cause it to overflow:

1. No base case. The function never stops calling itself.
2. Wrong direction. The function recurses but the argument doesn’t shrink — for example, factorial(N + 1) instead of factorial(N - 1).

Recursion vs Iteration

Both can solve the same problems — the difference is mostly expressiveness and cost.

The same idea, both ways

void countDown(int n) {
    while (n >= 1) {
        cout << n << " ";
        n--;
    }
}

def count_down(n):
    while n >= 1:
        print(n, end=" ")
        n -= 1

void countDown(int n) {
    if (n == 0) return;
    cout << n << " ";
    countDown(n - 1);
}

def count_down(n):
    if n == 0:
        return
    print(n, end=" ")
    count_down(n - 1)

Both work. For this problem iteration is clearly better — same complexity, less overhead. The recursive form really pays off for tree-shaped problems where the iterative version would need its own explicit stack.

Activity — try it both ways

Write a function to reverse a string, once iteratively and once recursively.

Types of Recursion

There are four shapes of direct recursion worth recognizing — and one for cross-function calls.

Types of Recursion

void printDown(int n) {
    if (n == 0) return;
    cout << n << " ";
    printDown(n - 1);   // ← last statement
}

void printUp(int n) {
    if (n == 0) return;
    printUp(n - 1);     // ← first statement
    cout << n << " ";   // happens on the way back up
}

int fib(int n) {
    if (n <= 1) return n;
    return fib(n - 1) + fib(n - 2);   // two recursive calls
}

int ackermann(int m, int n) {
    if (m == 0) return n + 1;
    if (n == 0) return ackermann(m - 1, 1);
    return ackermann(m - 1, ackermann(m, n - 1));  // nested!
}

bool isEven(int n) {
    if (n == 0) return true;
    return isOdd(n - 1);   // even(n) calls odd(n-1)
}
 
bool isOdd(int n) {
    if (n == 0) return false;
    return isEven(n - 1);  // odd(n) calls even(n-1)
}

What the runtime actually does

When you call a function, the language runtime:

1. Pushes a stack frame onto the call stack containing the function’s local variables, arguments, and return address.
2. Jumps to the function’s first instruction.
3. When the function returns, pops the frame and resumes the caller at the return address.

Recursion is just this same mechanism applied to itself. The stack tracks every “in-progress” call. Each return collapses one level. The reason recursion is so natural for trees is that the call stack already is a tree traversal in disguise.

Got the mental model? Next: how to design a recursive solution from scratch — without ever tracing through the call stack by hand.