🎓 A1Learner
🔍
0 of 40 lessons completed

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

Exercise

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