C Tutorial
C Recursion
A function that calls itself needs a base case. Without one, the call stack grows until it crashes.
A function that calls itself
Recursion is when a function calls its own name. Each call works on a smaller piece of the problem, then waits for that inner call to finish. The inner call may call again. That chain has to stop.
The stop condition is the base case: a path that returns without calling the function again. Every recursive function you write in this tutorial has one.
Countdown
countdown prints n, then calls itself with n - 1. Whenn is 0 or less, it prints done and returns. That is the base case.
Example
#include <stdio.h>
void countdown(int n) {
if (n <= 0) {
printf("done\n");
return;
}
printf("%d\n", n);
countdown(n - 1);
}
int main(void) {
countdown(3);
return 0;
}Output is 3, then 2, then 1, then done.
Open this in /c/try and change the starting number. The editor compiles with gcc as C17.
The base case comes first
Check the stop condition before you recurse. If you recurse first, the function never reaches the return. For countdown, the question is: is n already at zero? If yes, stop. If no, print and go one step smaller.
- Base case:
n <= 0— no further call. - Recursive case: print
n, thencountdown(n - 1).
The argument must move toward the base case. Here it decreases by one. If it stayed the same, you would never stop even with a base case written in the file.
Factorial
Factorial of n is n * (n - 1) * ... * 1. In code: if n is 0 or 1, the answer is 1. Otherwise it is n times factorial of n - 1.
Example
#include <stdio.h>
int factorial(int n) {
if (n <= 1) {
return 1;
}
return n * factorial(n - 1);
}
int main(void) {
printf("%d\n", factorial(5));
return 0;
}factorial(5) waits for factorial(4), which waits for 3, then 2, then 1. The base case returns 1. Then 2 * 1, 3 * 2, 4 * 6, 5 * 24. The program prints 120.
A missing base case crashes
Each call uses a frame on the call stack. If there is no base case, or the argument never reaches it, frames pile up until the program dies. gcc will not catch this at compile time. You get a runtime crash, often labeled a stack overflow.
Do not write a function that only calls itself with a larger n and never returns. There is no tidy compiler error. Add a base case before you call a recursive function from main.
Recursion or a loop
Countdown is also a for or while. A loop does not grow the stack. Prefer a loop when the steps are a simple counter. Recursion is clearer when a problem splits into a smaller copy of itself, such as walking a tree. For this tutorial, factorial and countdown are enough to see the pattern.
Next: store the address of a function and call it through a pointer.
Worked examples
The short listings above are there so you can see the grammar. The programs here use the same statements on quantities that already have units: a speed, a pH, a count of bases. They are classroom numbers. Air resistance is ignored. g is 9.81 m/s² unless a line says otherwise.
Open them in the C editor at /c/try. Change one measurement and check whether the result still has the right unit.
Maths
n!
n! is 1 × 2 × … × n. It also satisfies n! = n × (n−1)! with 0! = 1 and 1! = 1. That recurrence is the recursive function. 5! is 120.
Without the base case n < 2, the calls never stop. Factorial grows so fast that an int is already the wrong type by 13! on most desktops.
n! = n × (n−1)!
Example
#include <stdio.h>
int factorial(int n) {
if (n < 2) {
return 1;
}
return n * factorial(n - 1);
}
int main(void) {
printf("5! = %d\n", factorial(5));
return 0;
}Physics
Mass after n half-lives
Each recursive call halves the sample and subtracts one half-life. Three calls turn 8 g into 1 g. The call depth is n. An iterative loop does the same job with less stack; the recursive version matches the sentence “after one more half-life, half remains.”
mₙ = mₙ₋₁ / 2
Example
#include <stdio.h>
double after_halvings(double mass, int n) {
if (n <= 0) {
return mass;
}
return after_halvings(mass / 2.0, n - 1);
}
int main(void) {
printf("%.3f g left\n", after_halvings(8.0, 3));
return 0;
}