Before you begin
Why this matters
Recursion is how programs handle data that contains smaller copies of itself, such as directory trees or nested expressions. If you can follow one call at a time, you can predict what a recursive function prints and find out why one never stops or crashes.
What this helps you reason about
- Spot a function that can never stop calling itself, before you run the code.
- Predict the order of work done before and after a function calls itself.
- Choose a loop when the number of nested calls would grow with the size of the input.
A recursive function solves a problem by calling itself on a smaller version of the same problem. In C, each call gets its own copies of its arguments and its own local variables, which makes recursive calls easy to follow one at a time.
Already know this? The short version
- Each call gets its own copies of its parameters and its own local variables with automatic storage duration, which last until it returns; implementations keep them in a stack frame.
- A base case must exist and be reachable: unsigned n - 1 at 0 wraps to UINT_MAX, and signed overflow below INT_MIN is undefined behavior.
- Work before the recursive call runs on the way down, outermost call first; work after it runs on the way back, innermost call first.
- The stack size is set by the operating system (commonly 8 MB on Linux, see ulimit -s); the standard has no stack, so running out is outside what it defines (in practice, usually a segmentation fault), and the standard does not require tail-call optimization even though gcc and clang often perform it above -O0.
- An array parameter is a pointer, so recursing with a smaller count copies nothing; prefer a loop when depth grows with the input.
Words in this lesson (7)
- recursive function
- A function that calls itself. Each call works on a smaller version of the same problem.
- frame
- The record of one function call that has not finished: its parameters and local variables. It is created when the call starts and removed when the call returns. The C standard does not mention frames; it calls these variables automatic.
- call stack
- The frames of all calls that have not finished yet, with the newest on top. A new call adds a frame on top, and a return removes it. Only the newest call runs; each call below it waits for the call it made.
- base case
- The case, an input or a condition such as n == 0, that the function answers without calling itself. Reaching it stops the chain of calls.
- recursive case
- An input the function answers by calling itself on a smaller input and then using that answer.
- undefined behavior
- Code for which the C standard sets no requirements. The program may crash, print wrong results, or seem to work, and the result can change between builds.
- stack overflow
- The failure when calls go so deep that the stack runs out of space. The C standard has no stack, so it does not define what happens; on Linux the program usually ends with a segmentation fault.
Examples are focused snippets; imports, enclosing functions, or classes may be omitted. C examples use C11; Haskell examples use Haskell 2010. Expand the notes for language-specific depth.
01 / A call to itself
What happens when a function calls itself?
A recursive function is a function that calls itself. Each of those calls is a separate call: it gets its own copies of its parameters and its own local variables, which last until it returns.
countdown(3) prints 3 and calls countdown(2). That call prints 2 and calls countdown(1), and so on. Picture each active call as a box placed on top of the call that made it. Each box is called a frame: it holds one call’s parameters and local variables. The pile of frames is called the call stack. When a call finishes, its frame is removed, and the call underneath it continues.
The stepper shows the same picture. Its frame list has one frame for each active call, with the newest call at the top.
void countdown(int n) {
if (n == 0) {
printf("liftoff\n");
return;
}
printf("%d\n", n);
countdown(n - 1);
}Every call to countdown is a separate call with its own n.
Precisely: C does not mention a stack
The C standard says each call’s parameters and local variables have automatic storage duration: they exist until that call returns. Implementations almost always use a call stack for this, but the standard does not require one.
Experiment
Follow a countdown to its base case
Each call to countdown is a separate call with its own parameter. A call does not finish until the call it made has finished. So countdown(3) waits for countdown(2), countdown(2) waits for countdown(1), and countdown(1) waits for countdown(0).
Why it matters You can follow any recursive function the same way: one call at a time, each with its own values.
Predict how many countdown calls are active when liftoff prints. Then delete the base case (the whole if block) and run again.
#include <stdio.h>
void countdown(int n) {
if (n == 0) {
printf("liftoff\n");
return;
}
printf("%d\n", n);
countdown(n - 1);
}
int main(void) {
setvbuf(stdout, NULL, _IOLBF, 0); // line by line, as in a terminal
countdown(3);
return 0;
}
What to look for
Watch the frame list: each call to countdown adds one frame, with its own n. Without the base case, n goes below 0 and new frames keep appearing. The runner then ends the run with a message that begins "Stopped after". You will not see a segmentation fault: the runner stops long before the real stack runs out. The frame list shows only the newest 12 calls, so after that it stops growing. Watch n and the output instead: they keep falling.
Expected output
3
2
1
liftoff02 / Base case
What makes the recursion stop?
The base case is the case, an input or a condition, that the function answers directly, without calling itself. Every other input is the recursive case: the function calls itself with a smaller input. Without a base case, every call makes another call, and the program cannot finish on its own.
The calls must also reach the base case. countdown(n - 1) makes n smaller by one each time, so any positive int reaches 0. But with the test n == 0, countdown(-1) calls countdown(-2), then countdown(-3), and never reaches 0. The test n <= 0 makes every starting number stop.
void countdown(int n) {
if (n <= 0) {
printf("liftoff\n"); /* base case: answer directly */
return;
}
printf("%d\n", n);
countdown(n - 1); /* recursive case: a smaller input */
}Check two things: a base case exists, and every call gets closer to it.
Coming from Python: Python stops runaway recursion with a RecursionError after about 1,000 calls; C has no such check, so a missing base case runs until the stack is gone.
Precisely: an unsigned n
With unsigned int n, n can never be negative, but n - 1 when n is 0 wraps around to UINT_MAX. That is defined behavior for unsigned types, and the countdown would continue from UINT_MAX: 4294967295 where unsigned int is 32 bits, but 65535 where it is 16 bits. A signed int does not wrap: going below INT_MIN is undefined behavior, although the stack runs out long before that.
03 / The way back
What happens after the recursive call returns?
A recursive call pauses the current call; it does not end the current call. When visit(2) returns, visit(3) continues from the line after its recursive call.
So work written before the recursive call happens on the way down, while calls are still being made: visit(3) first, then visit(2), then visit(1). Work written after it happens on the way back, while the calls are returning and each paused call continues: visit(1) first, then visit(2), then visit(3).
void visit(int level) {
if (level == 0) {
return;
}
printf("enter %d\n", level);
visit(level - 1);
printf("leave %d\n", level);
}Code before the recursive call runs on the way down; code after it runs on the way back.
Experiment
Watch work happen on the way back
Each visit call prints its enter line, then makes its recursive call and pauses there. It prints its leave line only after the call it made has returned. So the newest call, visit(1), is the first to print leave.
Why it matters Where you put work relative to the recursive call decides its order. This is how a recursive function can reverse a sequence without a separate reverse step.
Predict the order of all six lines before running. Then move the leave line above the recursive call and predict again.
#include <stdio.h>
void visit(int level) {
if (level == 0) {
return;
}
printf("enter %d\n", level);
visit(level - 1);
printf("leave %d\n", level);
}
int main(void) {
setvbuf(stdout, NULL, _IOLBF, 0); // line by line, as in a terminal
visit(3);
return 0;
}
What to look for
Watch the output panel and the frame list together. The enter lines appear while frames are added: visit(3), then visit(2), then visit(1). The leave lines appear as frames are removed: leave 1 first, then leave 2, then leave 3. After the edit, each leave line comes right after its enter line, while calls are still being made: enter 3, leave 3, enter 2, leave 2, enter 1, leave 1.
Expected output
enter 3
enter 2
enter 1
leave 1
leave 2
leave 304 / Combining results
How do the answers come together?
Most recursive functions return a value. Each call asks a smaller version of the question and uses the answer. With values = {4, 2, 7}, total(values, 3) asks for the total of the first two values, which asks for the first one, which asks for none. Counting none is the base case: its total is 0.
The answers come back in order 0, 4, 6, 13: each call adds the last value in its range to the answer it received. Each addition waits until the call it depends on has returned.
int total(const int values[], int count) {
if (count == 0) {
return 0;
}
int rest = total(values, count - 1);
return rest + values[count - 1];
}
/* With int values[] = {4, 2, 7}: total(values, 3) is 13. */Assume the smaller call returns the right answer, then use it.
Precisely: the array is not copied
An array parameter is adjusted to a pointer to its first element, so every call shares the caller’s array. Only the pointer and count are copied into each call.
Experiment
Combine results from smaller calls
Each call answers a smaller version of the question and then uses that answer. The base case answers the smallest version directly. The results are combined on the way back, starting from the base case.
Why it matters You do not need to follow every call to check a recursive function. Check that the base case is right. Then check that each call combines a correct smaller answer correctly.
Predict what each call returns before running. Then change the 2 in the list to 5 and predict the new total.
#include <stdio.h>
int total(const int values[], int count) {
if (count == 0) {
return 0;
}
int rest = total(values, count - 1);
return rest + values[count - 1];
}
int main(void) {
setvbuf(stdout, NULL, _IOLBF, 0); // line by line, as in a terminal
int values[] = {4, 2, 7};
printf("%d\n", total(values, 3));
return 0;
}
What to look for
When the base case returns, select each earlier frame in turn. Each frame keeps its own count and receives the smaller call’s result as rest. values shows the same address and 4 in every frame: each call receives a pointer to the first element of the same array. The frame with count 0 also lists rest, with a leftover value: that call returns before rest is given a value. After the edit, the run prints 16.
Expected output
1305 / Depth
How deep can it go, and when is a loop better?
Each frame takes some memory, and the stack has a fixed size, set by the operating system. On Linux it is commonly 8 MB for the main thread, a limit you can change with ulimit -s. The C standard has no stack, so running out of it is outside what the standard defines. On Linux and similar systems, the program usually crashes with a segmentation fault and no other message. On a small device without memory protection, it may instead silently overwrite other data.
When the depth grows with the size of the input, such as one call per array element, a loop is usually the safer choice. Recursion fits best when the data itself is nested, like directories inside directories, where the depth stays small.
int total(const int values[], int count) {
int sum = 0;
for (int i = 0; i < count; i++) {
sum += values[i];
}
return sum;
}Use recursion when the problem is nested; prefer a loop when depth would grow with the input.
Coming from Java: Java turns a full stack into a StackOverflowError that can be caught; in C the standard does not define what happens, and the result is usually a crash with no message.
Precisely: optimizers may remove calls
At higher optimization levels, gcc and clang often turn a call in tail position into a jump, which removes the depth problem for that function. The standard does not require this, and the -O0 build the stepper uses keeps every call.
06 / Try it
Can you follow a fresh example?
Predict the output before revealing the answer. Ask where the print sits relative to the recursive call.
#include <stdio.h>
void show(int n) {
if (n == 0) {
return;
}
show(n - 1);
printf("%d\n", n);
}
int main(void) {
show(3);
return 0;
}
What does this print, and why in that order?
Reveal the reasoning
1, then 2, then 3. show(3) calls show(2), which calls show(1), which calls show(0). show(0) returns immediately. Then show(1) continues and prints 1, show(2) prints 2, and show(3) prints 3. The print comes after the recursive call, so it runs on the way back.
Practice tickets
- REC-101 · Fix the parcel check number → Free
- REC-102 · Count every nested folder → Sign in · Pro
- REC-103 · Show the reporting chain → Sign in · Pro