C Basics · beginner · ~20 min

Recursion — base case + smaller subproblem

Decompose a problem into a base case + a smaller instance of itself.

Overview

Recursion expresses 'do a small step, then solve the same problem on a smaller input'. Many divide-and-conquer algorithms (merge sort, quicksort, binary search) are most natural as recursion.

Why it matters

C has no built-in iteration helpers like Python's generators. Recursion is the cleanest way to express many algorithms on trees, lists, and substring problems.

Core concepts

Base case terminates the recursion. Recursive case reduces the problem and calls itself. Stack depth matters — each call adds a frame; a 10,000-deep recursion blows the typical 8 MB stack. For very deep recursion convert to iteration (explicit stack).

Pentester mindset. Parsers and decompressors are full of recursion; uncontrolled recursion depth on attacker-supplied input is a known DoS vector (XML billion-laughs, deeply-nested JSON, recursive PDF objects). Always cap depth.

Defensive coding habit. For any recursive function that accepts untrusted input, add a depth parameter and a hard limit. Refuse rather than crash.

Syntax notes

/* general shape */
T recurse(T input, int depth){
    if (depth > MAX_DEPTH) return ERROR;
    if (BASE_CONDITION(input)) return BASE_VALUE;
    return COMBINE(input, recurse(SMALLER(input), depth + 1));
}

Lesson

A recursive function calls itself with a strictly smaller input. Two things must be true for it to terminate: a base case that does NOT recurse, and a recursive case that approaches the base case.

Code examples

int factorial(int n){
    if (n <= 1) return 1;          /* base case */
    return n * factorial(n - 1);    /* recurses on smaller n */
}

Line by line

int fib(int n){
    if (n < 2) return n;             /* base case */
    return fib(n-1) + fib(n-2);      /* two recursive calls */
}
/* Note: this is O(2^n); the iterative version is O(n). */

Common mistakes

  • Forgetting the base case → infinite recursion → stack overflow.
  • Not making the recursive argument smaller → same problem.

Debugging tips

Print the input at the top of each call to see the unfolding. In gdb, bt shows the call stack — for a recursive crash, the stack tells you exactly how deep you went.

Memory safety

Uncontrolled recursion exhausts the stack and segfaults. Always cap depth for untrusted input.

Real-world uses

Tree traversal, parser combinators, divide-and-conquer sorts, file-system walkers, expression evaluators.

Practice tasks

  1. Implement factorial and fib recursively. 2. Add a depth cap. 3. Convert one to iteration with an explicit stack.

Summary

Recursion = base case + smaller subproblem. For untrusted input, always cap depth.

Practice with these exercises