A function that calls itself
Recursion solves a problem by solving a smaller version of the same problem. It needs exactly two parts, and missing either one is fatal.
After this lesson
You should be able to
- Identify the base case and the recursive case in a recursive function.
- Explain what happens when the base case is missing.
- Decide when recursion is clearer than a loop, and when it is not.
Two parts, both compulsory
A recursive function needs a base case — a size so small the answer is immediate — and a recursive case that does a little work and hands a smaller problem to itself. Counting down to zero: zero is the base case, and any other number prints itself then counts down from one less.
The recursive case must move towards the base case. If it does not shrink the problem, the function calls itself forever, each call using more memory, until the program crashes with a stack overflow.
void count_down(int n)
{
if (n == 0) { /* base case: stop */
printf("Liftoff\n");
return;
}
printf("%d\n", n);
count_down(n - 1); /* recursive case: smaller */
}Each call gets its own variables
When count_down(3) calls count_down(2), the first call does not end — it pauses, waiting. Both calls exist at once, each with its own n. There are now two boxes named n holding 3 and 2, which is why recursion works at all.
These paused calls stack up. That stack is finite, so deep recursion — tens of thousands of levels — runs out of space even when the logic is perfect.
When to use it
Recursion is clearest when the problem is naturally self-similar: a folder containing folders, a tree, or a definition that refers to itself. For plain counting, a loop is shorter, faster, and cannot overflow the stack.
Factorial and Fibonacci are taught recursively because they are small enough to trace by hand, not because recursion is the best way to compute them. Knowing that distinction is part of understanding the technique.
Try it yourself
Write a recursive function that returns the sum of the first n natural numbers, and say what its base case is.
Need a hint?
The sum of 1 to n is n plus the sum of 1 to n-1. What is the sum of 1 to 0?
Check the worked solution
The base case is n <= 0 returning 0, and using <= rather than == matters: a negative argument would otherwise skip the base case and recurse forever. The recursive case mirrors the mathematical definition line for line, which is the real appeal of recursion here.
#include <stdio.h>
int sum_to(int n)
{
if (n <= 0) /* base case */
return 0;
return n + sum_to(n - 1); /* recursive case */
}
int main(void)
{
printf("%d\n", sum_to(5)); /* 15 */
return 0;
}Quick check
What happens if a recursive function has no reachable base case?
Why this lesson exists
Syllabus mapping
The Nature of Recursion
Maps to course outcome CO4.