C Recursion and Base Cases
C Recursion and Base Cases
A classroom challenge asks for the sum from one to a small positive count. A recursive function can reduce the count until a simple stopping case remains.
Recursion is a function calling itself directly or indirectly. A correct recursive solution has a base case and a step that moves valid input toward that base case.
Explain
Trace calls toward a base case and returned values back to the caller.
Trace
Trace the same function for n = 4.
Apply
Recognize an input that does not move toward the stopping case.
Recursion: follow the data
Start
A classroom challenge asks for the sum from one to a small positive count. A recursive function can reduce the count until a simple stopping case remains.
Operation
Recursion is a function calling itself directly or indirectly. A correct recursive solution has a base case and a step that moves valid input toward that base case.
Result
Sum: 6
Understand the operation
For sum(3), the pending work becomes 3 + sum(2), then 2 + sum(1), then 1 + sum(0). The base call returns zero, after which earlier calls can finish their additions.
Each active call has its own automatic parameter object. A recursive name does not mean all calls share one changing n. This example’s contract accepts a small nonnegative integer.
Read the complete C program
This complete C17 program uses a small school example. Read declarations before the statements that use their values. Each printf format describes how the corresponding value is written to standard output.
C17 · complete program
#include <stdio.h>
static int sum(int n) {
if (n == 0) return 0;
return n + sum(n - 1);
}
int main(void) {
printf("Sum: %d\n", sum(3));
return 0;
}
Expected output
Sum: 6
Follow the values through the code
C17 · code used in this explanation
#include <stdio.h>
static int sum(int n) {
if (n == 0) return 0;
return n + sum(n - 1);
}
int main(void) {
printf("Sum: %d\n", sum(3));
return 0;
}
Calls descend through n values 3, 2, 1 and 0.
Returns produce 0, then 1, then 3 and finally 6. The result is built while pending calls finish.
Follow the worked calculation
Read the starting values
Calls descend through n values 3, 2, 1 and 0.
Perform the operation
Returns produce 0, then 1, then 3 and finally 6. The result is built while pending calls finish.
Check the observable result
Sum: 6
Sum: 6
Try a small variation
C17 · code used in this explanation
#include <stdio.h>
static int sum(int n) {
if (n == 0) return 0;
return n + sum(n - 1);
}
int main(void) {
printf("Sum: %d\n", sum(3));
return 0;
}
Trace the same function for n = 4.
Worked answer
The extra outer call adds four to sum(3), producing ten. The base case and the smaller-call relationship are unchanged.
C17 · complete program
#include <stdio.h>
static int sum(int n) {
if (n == 0) return 0;
return n + sum(n - 1);
}
int main(void) {
printf("Sum: %d\n", sum(4));
return 0;
}
Expected output
Sum: 10
Recognize the important boundaries
A negative n would move away from zero in this function. Validate the contract before calling rather than assume every integer terminates.
Deep recursion consumes call resources and can fail. Arithmetic can overflow even before stack resources run out; an iterative or bounded alternative may fit large input better.
Check your understanding
Choose the answer, then compare the reasoning for every option.
Use the idea independently
Recursion is a function calling itself directly or indirectly. A correct recursive solution has a base case and a step that moves valid input toward that base case.
Continue with a bounded recursive sum.
Language reference: WG14 C11 committee draft. These examples use the C17-compatible subset of the explained language features.
Reaching the recap and completing the quizzes are separate milestones.