🎓 A1Learner
🔍

C++ Recursion

Recursion is a way for a function to solve a problem through smaller calls of itself. Each call works on a smaller value than the call before it.

A countdown that calls itself

The countDown function prints its number first. It then calls itself with one less.

#include <iostream>

void countDown(int n) {
  if (n == 0) {
    return;
  }
  std::cout << n << std::endl;
  countDown(n - 1);
}

int main() {
  countDown(3);
  return 0;
}

Factorial by recursion

The factorial of a number is that number times the factorial of one less. The base case gives 1 for zero.

#include <iostream>

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

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

Example

#include <iostream>

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

int main() {
  std::cout << sumTo(10) << std::endl;
  return 0;
}

Key points

  • A recursive function calls itself with a smaller value each time.
  • The base case is the call that stops and makes no further call.
  • Each call should move the value closer to the base case.
  • The calls finish in reverse order as each one sends its result back.

In this example, sumTo adds its number to the sum of all smaller numbers. The call with 1 is the base case and sends back 1. The calls then add up to a total of 55.

Note

A missing base case makes the calls go on with no stopping call.

Try it Yourself

Edit the code, then press Run.

Running is simulated · Programiz C++ Compiler

Exercise

What is the job of the base case in a recursive function?