The STL and professional C++ · Lesson 20 of 21

Recursion

A function calling itself: the base case, the call stack, and memoization.

10 minutes2 games

Recursion solves a problem by having a function call itself on a smaller version of the same problem. It needs two things:

1. A base case: a small case answered directly, without recursing. 2. A step that shrinks the problem toward the base case.

C++

#include <iostream>
#include <string>

long long factorial(int n) {
    if (n <= 1) return 1;            // base case
    return n * factorial(n - 1);     // smaller problem
}

int digitSum(int n) {
    if (n < 10) return n;
    return n % 10 + digitSum(n / 10);
}

bool isPalindrome(const std::string& s, int i, int j) {
    if (i >= j) return true;
    return s[i] == s[j] && isPalindrome(s, i + 1, j - 1);
}

int main() {
    std::cout << factorial(5) << " " << factorial(20) << "\n";
    std::cout << digitSum(9045) << "\n";
    std::string w = "level";
    std::cout << isPalindrome(w, 0, static_cast<int>(w.size()) - 1) << "\n";
    return 0;
}

Step by step1 / 8

▶factorial(4)
2 4 * factorial(3)
3 3 * factorial(2)
4 2 * factorial(1)
5 return 1
6 return 2 * 1 = 2
7 return 3 * 2 = 6
8 return 4 * 6 = 24

Variables

stack

f(4)

Output

…

Each call waits for the one inside it. That's the call stack: it fills on the way down and empties on the way back.

Memoization: never compute the same thing twice

C++

#include <iostream>
#include <unordered_map>

long long calls = 0;

long long fibSlow(int n) {
    calls++;
    if (n < 2) return n;
    return fibSlow(n - 1) + fibSlow(n - 2);
}

std::unordered_map<int, long long> memo;
long long fibFast(int n) {
    calls++;
    if (n < 2) return n;
    auto it = memo.find(n);
    if (it != memo.end()) return it->second;
    return memo[n] = fibFast(n - 1) + fibFast(n - 2);
}

int main() {
    calls = 0;
    std::cout << fibSlow(30) << " in " << calls << " calls\n";
    calls = 0;
    std::cout << fibFast(30) << " in " << calls << " calls\n";
    return 0;
}

Spot the bug

This function overflows the stack for any positive number. Where's the problem?

Exercise

Write int power(int base, int exp) recursively (no loops, no pow), and print power(2, 10) and power(3, 4) on two lines.

Expected output:

1024
81

C++

#include <iostream>

int power(int base, int exp) {
    
}

int main() {
    std::cout << power(2, 10) << "\n";
    std::cout << power(3, 4) << "\n";
    return 0;
}

Learn more from

Played 0 of 2 games

#include <iostream> #include <string> long long factorial(int n) { if (n <= 1) return 1; // base case return n * factorial(n - 1); // smaller problem } int digitSum(int n) { if (n < 10) return n; return n % 10 + digitSum(n / 10); } bool isPalindrome(const std::string& s, int i, int j) { if (i >= j) return true; return s[i] == s[j] && isPalindrome(s, i + 1, j - 1); } int main() { std::cout << factorial(5) << " " << factorial(20) << "\n"; std::cout << digitSum(9045) << "\n"; std::string w = "level"; std::cout << isPalindrome(w, 0, static_cast<int>(w.size()) - 1) << "\n"; return 0; }