C/C++ Arena

Recursion explained

What recursion is, why every recursive function needs a base case, and how the call stack makes it work.

A recursive function calls itself on a smaller version of the problem. Every recursive function needs:

  1. A base case that answers directly without recursing, and
  2. A recursive case that moves toward the base case.

Each call gets its own stack frame with its own variables, so several calls are in progress at once. Without a base case the frames pile up until the program crashes with a stack overflow.

Recursion fits naturally with trees, divide and conquer (merge sort, quicksort) and anything defined in terms of itself.

Example

#include <stdio.h>

int sum_to(int n) {
    if (n == 0) return 0;
    return n + sum_to(n - 1);
}

int main(void) {
    printf("%d\n", sum_to(100));
    return 0;
}

Output:

5050

Watch it run: Recursion stacks up frames

Practice it