C++ Recursion

In this page:

Introduction to Recursion
Base Case and Recursive Case
Fibonacci Series
Stack Safety
Iterative vs Recursive

Introduction to Recursion

Recursion is when a function calls itself, using function calls instead of a loop's condition to control repetition. Each call works on a smaller piece of the original problem, and progress happens through the arguments changing on each call rather than a loop counter incrementing.

Example: Introduction to Recursion

cpp

#include <iostream>

int countdown(int n) {
	if (n == 0) return 0;
	std::cout << n << " ";
	return countdown(n - 1);
}

int main() {
	countdown(5);
	std::cout << std::endl;
	return 0;
}

Base Case and Recursive Case

Every recursive function needs a base case — a condition where it stops calling itself and simply returns a value directly — without one, the function would call itself indefinitely until it runs out of stack memory and crashes. The recursive case is the part that calls the function again, always moving closer to that base case.

Example: Base Case and Recursive Case

cpp

#include <iostream>

int factorial(int n) {
	if (n == 0) return 1;        // base case
	return n * factorial(n - 1); // recursive case
}

int main() {
	std::cout << factorial(5) << std::endl;
	return 0;
}

Fibonacci Series

The Fibonacci sequence, where each number is the sum of the two before it, maps naturally onto recursion: fib(n) = fib(n-1) + fib(n-2), with fib(0) and fib(1) as base cases. This mirrors the mathematical definition almost exactly, which is part of why recursion feels elegant here even though it's not the most efficient implementation.

Example: Fibonacci Series

cpp

#include <iostream>

int fib(int n) {
	if (n <= 1) return n;
	return fib(n - 1) + fib(n - 2);
}

int main() {
	for (int i = 0; i < 8; i++) {
		std::cout << fib(i) << " ";
	}
	std::cout << std::endl;
	return 0;
}

Stack Safety

Every recursive call adds a new frame to the program's call stack to track that call's local variables and where to resume afterward, and stacking up too many unfinished calls (deep recursion) can exhaust available stack memory, causing a stack overflow crash. This is why recursive solutions need a base case that's reliably reached within a reasonable number of calls.

Example: Stack Safety

cpp

#include <iostream>

int sumTo(int n) {
	if (n == 0) return 0;
	return n + sumTo(n - 1);
}

int main() {
	std::cout << sumTo(1000) << std::endl;
	// sumTo(1000000); // risks stack overflow: too many stacked call frames
	return 0;
}

Iterative vs Recursive

Nearly any recursive algorithm can be rewritten as an iterative loop instead, and iterative versions are usually faster and use significantly less memory, since they avoid the overhead of repeated function calls and stack frames. Recursion is often chosen anyway when it makes the code's logic dramatically clearer, such as with tree traversal.

Example: Iterative vs Recursive

cpp

#include <iostream>

int factorialRecursive(int n) {
	if (n == 0) return 1;
	return n * factorialRecursive(n - 1);
}

int factorialIterative(int n) {
	int result = 1;
	for (int i = 1; i <= n; i++) {
		result *= i;
	}
	return result;
}

int main() {
	std::cout << factorialRecursive(5) << " " << factorialIterative(5) << std::endl;
	return 0;
}

🔒

Chapter Quiz — Complete all 13 topics to unlock

0/13 topics done

Complete these topics first:

← Previous Lesson C++ Function Overloading Next Lesson → C++ Inline Functions