Recursion — base case + smaller subproblem

Overview

Recursion is a way of solving a problem by doing one small step and then asking a smaller version of the same problem to finish the job. Instead of writing a loop, a function calls itself on a simpler input, and keeps doing so until the input is so small the answer is obvious.

A helpful everyday picture: imagine you are standing in a long line and want to know your position. You cannot see the front, so you tap the person ahead and ask "what number are you?" They do not know either, so they ask the person ahead of them, and so on. Eventually the question reaches the person at the very front, who says "I am number 1." That answer flows back down the line: 1, then 2, then 3, until it reaches you. The "ask the person ahead" step is the recursive case; the front person answering "1" without asking anyone is the base case.

This lesson builds directly on two things you already know. From Functions you know how to define a function, pass arguments, and return a value — recursion is just a function that happens to call itself. From if / else you know how to branch on a condition — recursion needs a branch to decide "am I at the base case, or do I recurse?". Put those two ideas together and you have recursion.

In plain language first: a recursive function is one that calls itself with a smaller problem. In the standard terminology, every recursion has two parts — a base case that returns an answer directly, and a recursive case that reduces the problem and calls itself. Get both right and the function terminates with the correct answer.

Why it matters

Some data is naturally nested, and nested data is far easier to process with recursion than with a loop. A folder contains files and other folders, which contain more files and folders. An arithmetic expression like (2 + 3) * (4 - 1) contains smaller expressions inside it. HTML and JSON documents nest tags and objects inside one another. For all of these, a recursive function that says "handle this node, then handle each child the same way" mirrors the shape of the data exactly.

Many foundational algorithms are defined recursively and read most naturally that way: merge sort and quicksort split an array in half and sort each half; binary search repeatedly halves a sorted range; tree and graph traversals visit a node and then its neighbours. You will meet several of these in the practice exercises attached to this lesson.

Unlike some higher-level languages, C gives you no generators or built-in tree helpers. Recursion is one of the cleanest tools you have for expressing divide-and-conquer solutions. And because C runs close to the machine, recursion is also where you see the call stack directly — understanding it here makes stack overflows, segfaults, and backtraces in a debugger far less mysterious later.

Core concepts

1. The base case

Definition. The base case is the condition under which the function returns an answer without calling itself. It is the exit door of the recursion.

Plain-language explanation. Every recursion has to stop somewhere. The base case is the smallest, simplest input whose answer you already know: the factorial of 1 is 1; the sum of an empty list is 0; a search over an empty range finds nothing. When the input shrinks down to this size, the function answers directly instead of recursing.

How it works internally. When execution reaches the base case, the current function call finishes and hands a value back to whoever called it. That is the moment the chain of pending calls starts to unwind and results begin flowing back.

When to use / when not to. You need exactly the right base case: it must catch every way the input can bottom out. For factorial, n <= 1 is safer than n == 1, because n == 1 would recurse forever on n = 0 or negatives.

Common pitfall. A missing or unreachable base case means the function never stops calling itself, and the program crashes with a stack overflow.

2. The recursive case

Definition. The recursive case reduces the problem to a strictly smaller version of itself and calls the function again on that smaller input.

Plain-language explanation. This is the "ask the person ahead of me" step. You do a tiny piece of the work now (for factorial, remember to multiply by n), then delegate the rest to a smaller call (factorial(n - 1)), and finally combine the two.

How it works internally. The combine step usually looks like return SOMETHING(n) COMBINED_WITH recurse(smaller);. The recursive call must complete and return before the combine can finish, so the current call pauses mid-expression and waits.

When to use / when not to. The argument must move toward the base case on every call. factorial(n - 1) shrinks; factorial(n) or factorial(n + 1) does not and will loop forever.

Common pitfall. Recursing on an input that is not actually smaller (a typo like n instead of n - 1) — the base case is never reached.

Knowledge check. In factorial, what is the base case, and what single change to the recursive call would cause infinite recursion?

3. The call stack and stack frames

Definition. The call stack is a region of memory where each active function call gets its own stack frame holding that call's parameters and local variables. Recursion piles frames on top of one another.

How it works internally. Consider factorial(3). Each call gets pushed on top of the stack and stays there, paused, until the call it is waiting on returns. Then frames pop off one by one, carrying results back:

GROWING DOWN (calls pushed):
  factorial(3)  -> needs 3 * factorial(2)   [paused]
    factorial(2)  -> needs 2 * factorial(1) [paused]
      factorial(1)  -> base case, returns 1  <-- turning point

UNWINDING UP (results returned):
      factorial(1) = 1
    factorial(2) = 2 * 1 = 2
  factorial(3) = 3 * 2 = 6   -> final answer

Why it matters. Each frame consumes memory. The typical thread stack is around 8 MB. A recursion that goes tens of thousands of levels deep can exhaust it and crash with no clean error — a stack overflow. Deep-but-not-infinite recursion is a real risk, not only broken base cases.

When to use / when not to. Recursion is ideal when depth is naturally bounded and small (tree of height 20, array halved each step so depth ~log n). When depth can grow with input size — walking a million-node linked list — a loop, or a loop with an explicit stack, is safer.

Common pitfall. Assuming the compiler will always turn recursion into a loop. In C, that optimisation (tail-call elimination) is not guaranteed, so never rely on it for correctness.

Knowledge check. For factorial(5), how many stack frames exist at the deepest moment, just before the base case returns?

4. Recursion vs iteration

Many recursions have an equally valid loop form. Neither is universally better; they trade off differently.

The naive Fibonacci recursion also warns of a different cost: recomputing subproblems. fib(n) calls fib(n-1) and fib(n-2), which overlap heavily, giving roughly O(2^n) calls. An iterative version is O(n). Recursion clarity does not always mean recursion efficiency.

Knowledge check. Explain in your own words why the recursive factorial uses memory proportional to n, while an iterative version can use a constant amount.

5. Depth limiting for untrusted input

Definition. A depth-limited recursion carries an extra depth counter and refuses to go past a fixed maximum, returning an error instead of crashing.

Why it matters. Parsers and decompressors are full of recursion, and attacker-controlled nesting depth is a known denial-of-service vector (deeply nested JSON, the XML "billion laughs" pattern, recursively nested archive or document structures). Uncontrolled depth on hostile input turns "crash" into a weapon.

Defensive habit. For any recursion that processes input you did not create, add a depth parameter and a hard cap; reject input that exceeds it. This is defensive validation — it never runs against real targets, only your own programs.

Syntax notes

A recursive function is an ordinary function whose body calls itself. The shape is always: check the base case first, otherwise recurse on a smaller input and combine.

long factorial(int n) {
    if (n <= 1)                 /* base case: stop here, no self-call */
        return 1;
    return n * factorial(n - 1); /* recursive case: smaller n, then combine */
}

A depth-limited variant threads a counter through every call so untrusted input cannot recurse without bound:

#define MAX_DEPTH 1000

int process(const Node *node, int depth) {
    if (depth > MAX_DEPTH) return -1;      /* refuse: too deep */
    if (node == NULL)      return 0;       /* base case */
    return 1 + process(node->child, depth + 1); /* deeper -> depth + 1 */
}

Key points: the base-case test comes before the recursive call; the argument passed to the self-call is strictly closer to the base; and the return value usually combines the current step with the recursive result.

Lesson

A recursive function calls itself with a strictly smaller input.

For it to terminate, two things must be true:

• A base case that does not recurse.
• A recursive case that moves closer to the base case.

Code examples

#include <stdio.h>

/* Recursively sum the integers 1 + 2 + ... + n.
   Returns 0 for n <= 0. Uses long to reduce overflow risk. */
long sum_to_n(int n) {
    if (n <= 0)                     /* base case: nothing left to add */
        return 0;
    return n + sum_to_n(n - 1);     /* recurse on a strictly smaller n */
}

/* Classic recursive factorial: n! = n * (n-1)! with 0! = 1! = 1. */
long factorial(int n) {
    if (n <= 1)                     /* base case covers 0, 1, and negatives */
        return 1;
    return n * factorial(n - 1);
}

int main(void) {
    int n = 5;

    printf("sum_to_n(%d)  = %ld\n", n, sum_to_n(n));
    printf("factorial(%d) = %ld\n", n, factorial(n));

    /* Show the base case and a couple of small values. */
    for (int i = 0; i <= 4; i++)
        printf("factorial(%d) = %ld\n", i, factorial(i));

    return 0;
}

What it does. It computes two independent recursions and prints them. sum_to_n(5) adds 5 + 4 + 3 + 2 + 1. factorial(5) multiplies 5 * 4 * 3 * 2 * 1. The loop then prints factorials of 0 through 4 to make the base case visible.

Expected output:

sum_to_n(5)  = 15
factorial(5) = 120
factorial(0) = 1
factorial(1) = 1
factorial(2) = 2
factorial(3) = 6
factorial(4) = 24

Edge cases. sum_to_n(0) and factorial(0) both hit the base case immediately and return their identity values (0 and 1). Negative n is handled: sum_to_n returns 0, factorial returns 1, because both base tests use <=. Large n will overflow even long — factorial grows extremely fast (21! already exceeds a 64-bit signed range), which is a correctness limit of the type, not the recursion.

Line by line

We trace factorial(4) step by step. Each call checks n <= 1; if false it pauses to compute n * factorial(n - 1).

At step 4 the deepest frame returns 1. Now the stack unwinds, each paused call finishing its multiplication:

The final value 24 is handed back to main. Notice the pattern: the multiplications on the way down are all deferred — nothing is actually multiplied until the base case is hit and the calls unwind on the way up. That deferred work is exactly what the stack frames are holding for you: each frame remembers its own n so it can multiply once the smaller result arrives.

For sum_to_n(5) the same shape applies: it descends 5 -> 4 -> 3 -> 2 -> 1 -> 0, hits the base case returning 0, then adds back up 0 + 1 + 2 + 3 + 4 + 5 = 15.

Common mistakes

1. Forgetting the base case (or writing an unreachable one).

/* WRONG: never stops */
long factorial(int n) {
    return n * factorial(n - 1);   /* no base case at all */
}

Why it is wrong: there is no return that avoids the self-call, so the function recurses forever until the stack overflows and the program is killed. Fix: add the base case before recursing:

long factorial(int n) {
    if (n <= 1) return 1;          /* reachable base case */
    return n * factorial(n - 1);
}

How to spot it: the program crashes almost instantly, or a debugger backtrace shows thousands of identical frames.

2. Not shrinking the argument.

/* WRONG: n never changes */
long factorial(int n) {
    if (n <= 1) return 1;
    return n * factorial(n);       /* should be n - 1 */
}

Why it is wrong: the recursive call uses the same n, so the base case is never reached. Fix: pass n - 1. Prevention: after writing any recursive call, ask "is this argument strictly closer to the base case?"

3. Wrong base condition, missing an input.

/* RISKY: n == 1 misses n == 0 and negatives */
long factorial(int n) {
    if (n == 1) return 1;
    return n * factorial(n - 1);   /* factorial(0) -> factorial(-1) -> ... */
}

Why it is wrong: factorial(0) skips the base and recurses on -1, -2, ... forever. Fix: use n <= 1. Prevention: test the boundary inputs (0 and negatives), not just typical ones.

4. Assuming recursion is free. The naive fib below recomputes the same values exponentially:

long fib(int n) {
    if (n < 2) return n;
    return fib(n - 1) + fib(n - 2); /* correct, but O(2^n) calls */
}

It is correct, just slow for large n. Recognise when overlapping subproblems make a loop (or memoisation) the better choice.

Debugging tips

Compiler warnings. Enable them: gcc -Wall -Wextra -g rec.c -o rec. A warning like "control reaches end of non-void function" often means a code path forgot to return — sometimes the base case itself.

Runtime: stack overflow / segfault. If the program crashes immediately or after growing memory, suspect a missing base case or a non-shrinking argument. Reproduce with a small input first so the bug appears before the machine is stressed.

Trace with print statements. Print the argument at the top of each call to watch the recursion unfold, and print the return value to watch it unwind:

long factorial(int n) {
    printf("enter n=%d\n", n);
    long r = (n <= 1) ? 1 : n * factorial(n - 1);
    printf("leave n=%d -> %ld\n", n, r);
    return r;
}

A correct recursion shows a clean descending ladder of enter lines, then an ascending ladder of leave lines. If enter lines keep going and never turn around, the base case is not being reached.

Use a debugger. In gdb, run the program, and after a crash type bt (backtrace). Thousands of identical frames confirm runaway recursion; the frame count also tells you roughly how deep it got. You can set bt 20 to limit output.

Questions to ask when it does not work. Does a base case exist and is it checked before the recursive call? Is the recursive argument strictly smaller every time? Does the base case catch 0 and negative inputs, not just the happy path? Is the recursion simply deep rather than infinite (needs a loop instead)?

Memory safety

Stack exhaustion is the headline risk. Every recursive call consumes a stack frame, and the stack is finite (commonly ~8 MB per thread). Runaway recursion — from a missing base case, a non-shrinking argument, or simply legitimate but very deep input — overflows the stack and produces undefined behaviour, typically a segfault with no clean error message. Recursion depth is effectively an unchecked resource unless you bound it.

Bound depth on untrusted input. If a recursive function processes data from a file, the network, or any source you do not control, an attacker can choose the nesting depth and force a crash — a denial-of-service. This is the pattern behind deeply nested JSON and the XML "billion laughs" expansion. Defensive fix: thread a depth counter through every call and refuse input past a fixed cap:

long sum_to_n_safe(int n, int depth) {
    if (depth > 100000) return -1;   /* refuse pathological depth */
    if (n <= 0)         return 0;    /* base case */
    return n + sum_to_n_safe(n - 1, depth + 1);
}

This is defensive, lab-only validation of your own program's robustness — never anything aimed at a real system.

Other memory concerns specific to recursion. Local arrays declared inside a recursive function are re-created in every frame, multiplying stack use — a 1 KB local buffer times 5000 levels is 5 MB. Prefer small locals in recursive functions. If a recursive function allocates with malloc, make sure every path (including error and base-case paths) still frees or hands off ownership, or you leak once per level. And beware integer overflow in the result: factorial and Fibonacci overflow their integer type long before they overflow the stack, so validate input ranges too.

Real-world uses

Concrete uses. Recursion underpins a great deal of real software: file-system walkers that descend directory trees (the logic behind find or a recursive du); parsers and interpreters that evaluate nested expressions and JSON/XML documents; the divide-and-conquer sorts merge sort and quicksort in standard libraries; binary search over sorted data; traversals of trees and graphs in databases, compilers, and game AI; and flood-fill / maze-solving in graphics and games. Several of these appear in this lesson's exercises — recursive binary search and the Tower of Hanoi move count among them.

Professional best-practice habits.

Beginners should focus on: writing the base case first and testing boundary inputs (0, negative, empty); naming the function and parameters for what they mean; keeping the recursive step obviously smaller; and adding a comment marking the base case. Verify with a hand trace on a tiny input before trusting the code.

Advanced practitioners additionally: bound recursion depth for any untrusted input; prefer iteration or an explicit stack when depth scales with input size; watch for overlapping subproblems and apply memoisation; keep locals in recursive functions tiny to conserve stack; and document the maximum expected depth so reviewers can reason about stack safety. Across both levels, the durable habits are validation, clear error returns, cleanup on every path, and choosing recursion only where it genuinely clarifies the code.

Practice tasks

Beginner 1 — Recursive countdown. Write void countdown(int n) that prints n, n-1, ..., 1 each on its own line, then prints "Liftoff!". Requirements: the base case is n <= 0 (print only "Liftoff!"); the recursive case prints n then calls countdown(n - 1). Example: countdown(3) prints 3, 2, 1, Liftoff!. Concepts: base case, recursive case, ordering work before the recursive call.

Beginner 2 — Recursive sum. Implement long sum_to_n(int n) returning 1 + 2 + ... + n, and 0 when n <= 0. Verify sum_to_n(5) == 15 and sum_to_n(0) == 0. Constraint: no loops. Hint: n + sum_to_n(n - 1). Concepts: combining the current value with the recursive result. (Matches the Sum 1..n recursively exercise.)

Intermediate 1 — Recursive integer power. Implement long int_power(int base, int exp) for exp >= 0, using base^exp = base * base^(exp - 1) with base case base^0 = 1. Example: int_power(2, 10) == 1024. Constraint: recursion only, exp guaranteed non-negative. Hint: watch that the base case is exp == 0, not exp == 1. Concepts: choosing the right base value, shrinking a different parameter.

Intermediate 2 — Recursive binary search. Implement int bsearch_rec(const int *a, int lo, int hi, int target) that searches the sorted half-open range [lo, hi) and returns an index of target, or -1 if absent. Requirements: base case is an empty range (lo >= hi) returning -1; otherwise compare target with the middle element and recurse into the correct half. Example: searching {1,3,5,7,9} for 7 returns 3. Concepts: divide-and-conquer, log-depth recursion, correct range boundaries. (Matches the Binary search (recursive) exercise.)

Challenge — Depth-limited nesting counter. Write int max_depth(const char *s, int limit) that returns the maximum nesting depth of balanced parentheses in s (e.g. "(())()" -> 2), but returns -1 if the depth would exceed limit or the parentheses are unbalanced. Model this as a recursion (or a scan with a depth counter) that increments on '(', decrements on ')', and refuses to exceed limit. Constraints: treat s as untrusted input; never recurse (or count) past limit; reject a ')' that has no matching '('. Hint: track current depth and the running maximum; this mirrors how a hardened parser caps attacker-controlled nesting. Concepts: depth limiting, defensive validation, base case as an error return.

Summary

Recursion solves a problem by combining a base case (an input small enough to answer directly, with no self-call) and a recursive case (do one small step, then call yourself on a strictly smaller input and combine the results). Both parts are mandatory: the base case makes it stop, and the shrinking argument makes it reach that stop.

The key syntax is a function that tests the base condition before calling itself: if (base) return value; else return combine(x, f(smaller));. Internally, each call gets a stack frame; calls pile up on the way down and unwind on the way back, which is why deep recursion costs memory and can overflow the stack.

The most common mistakes are a missing or unreachable base case, an argument that never shrinks, and a base condition that misses 0 or negative inputs — all of which cause infinite recursion and a crash. Also remember that correct is not the same as efficient: naive Fibonacci is O(2^n).

What to remember: write the base case first, prove the argument shrinks every call, test the boundaries, and — for any recursion over input you do not control — cap the depth and refuse pathological input rather than let it crash your program.

Practice with these exercises

• Sum 1..n recursively
• Integer power recursively
• Factorial
• Nth Fibonacci
• Binary search (recursive implementation)
• Tower of Hanoi: count moves