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:

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

Syntax

cpp

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

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 std::cout and std::cin
#include <iostream>

int countdown(int n) {
	if (n == 0) return 0;
	// Print to the console with cout
	std::cout << n << " ";
	// Send countdown(n - 1) back to the caller
	return countdown(n - 1);
}

// Program execution starts in main()
int main() {
	countdown(5);
	// Print to the console with cout
	std::cout << std::endl;
	// Return 0 to signal that the program finished successfully
	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 std::cout and std::cin
#include <iostream>

int fib(int n) {
	if (n <= 1) return n;
	// Send fib(n - 1) + fib(n - 2) back to the caller
	return fib(n - 1) + fib(n - 2);
}

// Program execution starts in main()
int main() {
	// Loop: repeat while the condition holds
	for (int i = 0; i < 8; i++) {
		// Print to the console with cout
		std::cout << fib(i) << " ";
	}
	// Print to the console with cout
	std::cout << std::endl;
	// Return 0 to signal that the program finished successfully
	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 std::cout and std::cin
#include <iostream>

int factorialRecursive(int n) {
	if (n == 0) return 1;
	// Send n * factorialRecursive(n - 1) back to the caller
	return n * factorialRecursive(n - 1);
}

int factorialIterative(int n) {
	// Declare result and set it to 1
	int result = 1;
	// Loop: repeat while the condition holds
	for (int i = 1; i <= n; i++) {
		result *= i;
	}
	// Send result back to the caller
	return result;
}

// Program execution starts in main()
int main() {
	// Print to the console with cout
	std::cout << factorialRecursive(5) << " " << factorialIterative(5) << std::endl;
	// Return 0 to signal that the program finished successfully
	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