C Recursion

In this page:

What is Recursion?
The Base Case
Recursive Factorial
Sum of First N Numbers
Stack Overflow Warning

What is Recursion?

Recursion happens when a function calls itself, directly or indirectly, letting you express a solution as a smaller version of the same problem -- useful for tasks that naturally break down into repeated, self-similar steps.

Example: What is Recursion?

#include <stdio.h>
void countdown(int n) {
	if (n == 0) return;
	printf("%d ", n);
	countdown(n - 1);
}
int main() {
	countdown(3);
	return 0;
}

The Base Case

Every recursive function needs a base case -- a condition where it stops calling itself and simply returns a value -- without one, each call spawns another call indefinitely until the program crashes.

Example: The Base Case

#include <stdio.h>
int factorial(int n) {
	if (n == 0) {
		return 1;
	}
	return n * factorial(n - 1);
}
int main() {
	printf("%d", factorial(4));
	return 0;
}

Recursive Factorial

Computing a factorial recursively expresses N! as N times (N-1)!, with the base case being that 0! equals 1 -- each recursive call handles one step smaller than the last until it reaches that stopping point.

Example: Recursive Factorial

#include <stdio.h>
int factorial(int n) {
	if (n == 0) {
		return 1;
	}
	return n * factorial(n - 1);
}
int main() {
	printf("%d", factorial(5));
	return 0;
}

Sum of First N Numbers

Summing the numbers from 1 to N recursively works the same way: the sum of N is N plus the sum of (N-1), continuing to shrink the problem by one each call until it reaches a base case of 0 or 1.

Example: Sum of First N Numbers

#include <stdio.h>
int sum(int n) {
	if (n <= 1) {
		return n;
	}
	return n + sum(n - 1);
}
int main() {
	printf("%d", sum(5));
	return 0;
}

Stack Overflow Warning

Each recursive call reserves its own space on the program's call stack to track its local variables and return address; recursion that never reaches its base case (or goes too deep) exhausts that stack and crashes with a stack overflow.

Example: Stack Overflow Warning

#include <stdio.h>
int factorial(int n) {
	if (n == 0) {
		return 1;
	}
	return n * factorial(n - 1);
}
int main() {
	printf("%d", factorial(4));
	return 0;
}

🔒

Chapter Quiz — Complete all 8 topics to unlock

0/8 topics done

Complete these topics first:

← Previous Lesson C Function Prototypes Next Lesson → C Scope & Lifetime