C++ Recursion

beginner c++11

In C++, or any programming language, a recursive function is a function that calls itself. Recursive functions are useful because they can express processes that repeat based on previous values. The most important thing to remember about recursive functions is to have a base case. A base case is one where the parameters of the function result in the function not recursively calling itself, but instead returning some fixed value. Otherwise the recursion would never end and your program would never finish! Two common examples of recursive functions are the factorial math expression (N!) and the Fibonacci sequence (0 1 1 2 3 5 8 …).

Factorial

Factorials are calculated by repeatedly multiplying a number by itself minus 1 until we reach 1 (N! = N * N-1 * ... * 1).

#include <iostream>

// Calculate the factorial of N, or N!
// The factorial of N is N * N-1 * N-2 ... * 1
// 7! = 7 * 6 * 5 * 4 * 3 * 2 * 1
uint64_t factorial(uint64_t n) {
  if (n == 0 || n == 1) {
    return 1;
  }
  return n * factorial(n - 1); 
}

int main() {
  std::cout << factorial(7) << "\n";
}

5040

Fibonacci

The Nth Fibonacci number is calculated by summing N-1 and N-2 (N = N-1 + N-2).

#include <iostream>

// Calculate the Nth fibonacci number where 0 is the 0th number
// The Fibonacci rule is the Nth number is equal to the sum of the
// previous two numbers, so N = (N-1) + (N-2)
// The first two numbers should be 0 and 1
// The first 8 Fibonacci numbers are 0, 1, 1, 2, 3, 5, 8, 13
uint64_t fibonacci(uint64_t n) {
  if (n == 0) {
    return 0; 
  } else if (n == 1) {
    return 1;
  }
  return fibonacci(n - 1) + fibonacci(n - 2);
}

int main() {
  std::cout << fibonacci(7) << "\n";
}

13