C++ Recursion

What is Recursion?

A recursive function is a function that calls itself. Each call works on a smaller piece of the problem. To keep the calls from going forever, every recursive function needs a base case: a simple condition that stops the recursion and returns a direct answer.

• Base case: the condition that stops the recursion.
• Recursive case: the part where the function calls itself with a smaller input.
• Progress: each call must move closer to the base case.

A Simple Example: Sum of Numbers

Suppose you want to add all numbers from n down to 1. You can say the sum of n is n plus the sum of everything below it. The base case is when n reaches 0, where the sum is simply 0.

#include <iostream>
using namespace std;

int sumTo(int n) {
  if (n <= 0) {
    return 0; // base case
  }
  return n + sumTo(n - 1); // recursive case
}

int main() {
  cout << sumTo(5) << endl; // 5 + 4 + 3 + 2 + 1 = 15
  return 0;
}

Calculating a Factorial

Factorial is a classic recursion example. The factorial of n (written n!) is n times the factorial of n minus 1, and the factorial of 0 is defined as 1. That definition maps directly onto a recursive function.

#include <iostream>
using namespace std;

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

int main() {
  cout << "5! = " << factorial(5) << endl; // 120
  return 0;
}