Recursion

A recursive function solves a problem by calling itself on a smaller input. The loop from lesson 14 and a recursion can compute the same result, but the recursion uses the call stack as its state. Two things make it work: a base case that stops the calls, and an argument that moves toward that base case.

A function that calls itself

The factorial of n is n times the factorial of n - 1, and the factorial of 1 is 1. The second sentence is the base case; without it the function would call itself forever. The return type is long because 10! does not fit in a signed int on this machine, a range question from lesson 6.

#include <stdio.h> static long factorial(int n) { if (n <= 1) { return 1; } return n * factorial(n - 1); } int main(void) { printf("5! = %ld\n", factorial(5)); printf("10! = %ld\n", factorial(10)); return 0; }

gcc -Wall -Wextra factorial.c -o factorial
./factorial

5! = 120
10! = 3628800

static on the function keeps the name inside this file; lesson 18 takes that keyword apart. The recursion itself is a straight translation of the definition, which is why it is easier to check than the loop version.

The call stack

Every call creates a stack frame holding the parameters and the return address, and the frames are released in reverse order. Printing on the way in and on the way out shows the shape. The example sums the digits of 472 by peeling off one digit per call.

#include <stdio.h> static int sum_digits(int n, int depth) { printf("%*senter %d\n", depth * 2, "", n); if (n < 10) { printf("%*sreturn %d\n", depth * 2, "", n); return n; } int total = n % 10 + sum_digits(n / 10, depth + 1); printf("%*sreturn %d\n", depth * 2, "", total); return total; } int main(void) { printf("total: %d\n", sum_digits(472, 0)); return 0; }

gcc -Wall -Wextra trace.c -o trace
./trace

enter 472
enter 47
enter 4
return 4
return 11
return 13
total: 13

The indentation comes from %*s with a width of depth * 2. The deepest call returns first, and each parent adds its own digit on the way back: 2 + 1 + 4 in reverse order.

Repeated work

The Fibonacci definition calls itself twice, once for n - 1 and once for n - 2. That is correct and very slow: the second subtree recomputes almost everything the first one already computed. A counter in a file scope variable makes the cost visible.

#include <stdio.h> static int calls = 0; static int fib(int n) { calls++; if (n < 2) { return n; } return fib(n - 1) + fib(n - 2); } int main(void) { printf("fib(10) = %d\n", fib(10)); printf("calls: %d\n", calls); return 0; }

gcc -Wall -Wextra fib.c -o fib
./fib

fib(10) = 55
calls: 177

Fifty-five is the eleventh Fibonacci number, and reaching it took 177 calls. Each extra n roughly multiplies the work by the golden ratio, so fib(40) would need tens of millions of calls; an iterative loop or a memo keeps the same definition at linear cost.

Base case and progress

Euclid's algorithm is the cleanest recursion in the language: the greatest common divisor of a and b is the divisor of b and a % b, and when b is zero the answer is a. The second argument strictly decreases, so the base case is reached after a logarithmic number of steps.

#include <stdio.h> static int gcd(int a, int b) { if (b == 0) { return a; } return gcd(b, a % b); } int main(void) { printf("gcd(1071, 462) = %d\n", gcd(1071, 462)); printf("gcd(17, 5) = %d\n", gcd(17, 5)); return 0; }

gcc -Wall -Wextra gcd.c -o gcd
./gcd

gcd(1071, 462) = 21
gcd(17, 5) = 1

Two numbers are coprime when the result is 1, as in the second line. Before writing a recursion, find the measure that decreases at every call: a smaller number, a shorter string, a smaller array range. If no such measure exists, the loop is the safer tool.

No base case

A recursion without a stop condition is caught by GCC before it runs; the warning even points at the recursive call. The program is still built, and running it fills the stack until the process crashes.

#include <stdio.h> static int down(int n) { return down(n + 1) + 1; } int main(void) { printf("%d\n", down(0)); return 0; }

gcc -Wall -Wextra infinite.c -o infinite

infinite.c: In function 'down':
infinite.c:3:12: warning: infinite recursion detected [-Winfinite-recursion]
3 | static int down(int n)
| ^~~~
infinite.c:5:12: note: recursive call
5 | return down(n + 1) + 1;
| ^~~~~~~~~~~

Running the binary ends with a segmentation fault, and the exit status is 139. A debugger shows the same function repeated in the backtrace; the depth depends on the stack limit of the process, so the numbers differ between runs:

gcc -g -O0 -Wall -Wextra infinite.c -o infinite_g
gdb -batch -ex 'set disable-randomization off' -ex run -ex 'bt 6' ./infinite_g

Program received signal SIGSEGV, Segmentation fault.
0x000056262d34a18d in down (n=<error reading variable: Cannot access memory at address 0x7ffdbb33effc>) at infinite.c:4
4 {
#0 0x000056262d34a18d in down (n=<error reading variable: Cannot access memory at address 0x7ffdbb33effc>) at infinite.c:4
#1 0x000056262d34a19d in down (n=261948) at infinite.c:5
#2 0x000056262d34a19d in down (n=261947) at infinite.c:5
#3 0x000056262d34a19d in down (n=261946) at infinite.c:5
#4 0x000056262d34a19d in down (n=261945) at infinite.c:5
#5 0x000056262d34a19d in down (n=261944) at infinite.c:5

A missing stop condition is the extreme case of a recursion that does not make progress. A base case that is never reached, for example one that tests for zero while the argument grows, fails in exactly the same way.

Exercises

1. Write a recursive power function for an unsigned exponent and compare its call count with the loop version for exponent 10.
2. Print a number in binary with a recursion that divides by two, and check the output against lesson 11.
3. Turn the Fibonacci recursion into an iterative loop and check that both return the same values up to 20 without an overflow.

The code on this page was run with gcc (Alpine 15.2.0) 15.2.0 on Alpine Linux 3.24.3 (x86_64) in a Docker container.

Article author: Arthur Isaev