C, lesson 11
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:
If the recursive case doesn't get closer to the base case, the function calls itself forever.
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.
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.
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.
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.
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.
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
0Input:
4 5
..#..
..#..
###..
.....
0 0
Output:
Filled: 4
~~#..
~~#..
###..
.....