Learn/C/11. Recursion
Lesson 11 of 15
Sign in

C, lesson 11

Recursion

A recursive function is one that calls itself. That sounds circular, but it works as long as each call works on a smaller version of the problem and there is a version small enough to answer directly. Many problems have this shape: a folder contains folders, a sentence contains words, a maze is one step plus a smaller maze.

Every recursive function needs both parts:

  • a base case that returns without recursing, and
  • a recursive case that moves toward the base case.

If the recursive case doesn't get closer to the base case, the function calls itself forever.

What happens in memory

Each call gets its own fresh set of parameters and local variables, stored in a block of memory called a stack frame. When factorial(4) runs, it waits for factorial(3), which waits for factorial(2), which waits for factorial(1). That one returns 1, and the waiting calls finish in reverse order: 2, then 6, then 24.

2 exercises to try what you just read.

Exercise 1

Digit sum

Press Ctrl Enter or Check to test your code.

Exercise 2

Paint bucket

Press Ctrl Enter or Check to test your code.

The stack is limited (often a few megabytes). Recursing millions of levels deep, or forever, overflows it and the program crashes with a segmentation fault. For problems that need only a few thousand levels, recursion is perfectly safe.

Thinking recursively

Don't try to trace every call in your head. Instead, trust that the recursive call works for the smaller input and ask: "given the answer for the smaller problem, how do I build the answer for this one?"

Counting the digits of a number: a number below 10 has one digit; otherwise it has one more digit than the number with its last digit removed.

Printing a number in binary uses the same idea. The order of the two lines matters: recursing first prints the higher bits before the current one.

Branching recursion

Some problems split into several smaller problems. Exploring a grid is the classic example: from one cell, explore each neighbour. Mark cells as visited before you recurse, or the calls bounce back and forth forever.

Recursion or a loop?

Anything recursive can be written with a loop and your own stack, and simple cases like factorial are usually clearer as loops in C. Recursion shines when the data itself is nested or branching: trees, grids, mazes, expressions with parentheses. Beware of naive branching recursion that recomputes the same answers: the textbook recursive Fibonacci makes an exponential number of calls.

Further reading

  • GNU C Manual: Recursive Functions
  • cppreference: Function definitions
  • cppreference: return statement

Write a recursive function int digit_sum(long long n) that returns the sum of the decimal digits of n (for negative numbers, use the digits of its absolute value). Read integers until the input ends and print each digit sum on its own line.

Base case hint: a number from 0 to 9 is its own digit sum.

A paint program fills an area with one click. Read the grid size rows cols (each 1 to 20), then rows lines of cols characters, where . is empty canvas and # is a wall. Then read the clicked cell r c (0-based row and column, always inside the grid).

If the clicked cell is ., fill it and every . connected to it up, down, left or right (not diagonally) with ~. If it is #, nothing changes. Print Filled: <count> followed by the grid.

Write a recursive int fill(int r, int c) that returns how many cells it painted.

long long factorial(int n) {
    if (n <= 1) {
        return 1;                    // base case: answer directly
    }
    return n * factorial(n - 1);     // recursive case: a smaller problem
}
int count_digits(int n) {
    if (n < 10) {
        return 1;
    }
    return 1 + count_digits(n / 10);
}
void print_binary(unsigned n) {
    if (n >= 2) {
        print_binary(n / 2);
    }
    putchar('0' + n % 2);
}
void explore(int r, int c) {
    if (r < 0 || r >= rows || c < 0 || c >= cols) return;  // off the map
    if (visited[r][c]) return;                             // seen already
    visited[r][c] = true;
    explore(r + 1, c);
    explore(r - 1, c);
    explore(r, c + 1);
    explore(r, c - 1);
}
Input:
1234 -507 0
Output:
10
12
0
Input:
4 5
..#..
..#..
###..
.....
0 0
Output:
Filled: 4
~~#..
~~#..
###..
.....