C Recursion

Recursion is when a function solves a big problem by calling itself on a smaller piece, like nesting dolls with smaller dolls inside. It stops at the smallest doll.

In this page:

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

Syntax

return_type function_name(parameters) {
  if (base_case_condition) {
    return base_value;
  }
  return function_name(smaller_input);  // recursive case
}

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 standard input/output (printf, scanf)
#include <stdio.h>
void countdown(int n) {
	if (n == 0) return;
	// Print formatted text to the screen
	printf("%d ", n);
	countdown(n - 1);
}
// Program execution starts in main()
int main() {
	countdown(3);
	// Return 0 to signal that the program finished successfully
	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 standard input/output (printf, scanf)
#include <stdio.h>
int factorial(int n) {
	// Check whether n == 0
	if (n == 0) {
		// Send 1 back to the caller
		return 1;
	}
	// Send n * factorial(n - 1) back to the caller
	return n * factorial(n - 1);
}
// Program execution starts in main()
int main() {
	// Print formatted text to the screen
	printf("%d", factorial(4));
	// Return 0 to signal that the program finished successfully
	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 standard input/output (printf, scanf)
#include <stdio.h>
int factorial(int n) {
	// Check whether n == 0
	if (n == 0) {
		// Send 1 back to the caller
		return 1;
	}
	// Send n * factorial(n - 1) back to the caller
	return n * factorial(n - 1);
}
// Program execution starts in main()
int main() {
	// Print formatted text to the screen
	printf("%d", factorial(5));
	// Return 0 to signal that the program finished successfully
	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 standard input/output (printf, scanf)
#include <stdio.h>
int sum(int n) {
	// Check whether n <= 1
	if (n <= 1) {
		// Send n back to the caller
		return n;
	}
	// Send n + sum(n - 1) back to the caller
	return n + sum(n - 1);
}
// Program execution starts in main()
int main() {
	// Print formatted text to the screen
	printf("%d", sum(5));
	// Return 0 to signal that the program finished successfully
	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 standard input/output (printf, scanf)
#include <stdio.h>
int factorial(int n) {
	// Check whether n == 0
	if (n == 0) {
		// Send 1 back to the caller
		return 1;
	}
	// Send n * factorial(n - 1) back to the caller
	return n * factorial(n - 1);
}
// Program execution starts in main()
int main() {
	// Print formatted text to the screen
	printf("%d", factorial(4));
	// Return 0 to signal that the program finished successfully
	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