Learn/C++/11. Recursion
Lesson 11 of 15
Sign in

C++, lesson 11

Recursion

A function is recursive when it calls itself. The idea is to solve a problem by solving a smaller copy of the same problem, until the copy is so small that the answer is obvious.

Every recursive function needs:

  1. A base case that returns an answer without recursing.
  2. A recursive case that calls the function on input that is closer to the base case.

Miss either one, or make a recursive call that doesn't shrink the problem, and the function calls itself until the program runs out of stack memory and crashes.

The call stack

Each call gets its own copy of its parameters and local variables in a stack frame. When power(2, 3) runs, it waits for power(2, 2), which waits for power(2, 1), which waits for power(2, 0). That one returns 1, and the waiting calls finish one by one: 2, 4, 8. The stack has a limited size (typically a few megabytes), so depths of a few thousand are fine, but a million levels is not.

2 exercises to try what you just read.

Exercise 1

Anagram maker

Press Ctrl Enter or Check to test your code.

Exercise 2

Nested list sum

Press Ctrl Enter or Check to test your code.

Trust the recursion

When you write a recursive function, don't trace every call. Assume the call on the smaller input already works, and only ask how to use its answer. To reverse a string: the reverse of "abc" is the reverse of "bc" followed by 'a'.

Recursion that branches: backtracking

Some problems are a series of choices: pick a letter, then pick another from what's left. Backtracking explores every choice: make a choice, recurse to handle the rest, then undo the choice and try the next one. The undo step is what lets one shared variable serve all branches.

Passing chosen by reference avoids copying the vector at every level, which is why the undo matters.

Recursion and nested data

Data that contains smaller versions of itself is recursive by nature: folders inside folders, lists inside lists, expressions inside parentheses. A function that processes such data can call itself whenever it meets a nested part. Parsers are often written this way (a recursive descent parser): a function reads one item, and if that item is itself a list, it calls itself to read the inner list. Passing the current position by reference (std::size_t& pos) lets every level share one cursor into the text.

When not to recurse

Simple counting problems such as factorial or summing a vector are clearer as loops. And watch for repeated work: the naive recursive Fibonacci recomputes the same values exponentially many times. Use recursion where the problem branches or nests.

Further reading

  • cppreference: Function declaration
  • cppreference: return statement
  • cppreference: std::string::substr

Read one word of distinct lowercase letters (1 to 7 letters). Print every arrangement of its letters in alphabetical order, one per line, and then Total: <count>.

Plan: sort the letters first (std::sort(word.begin(), word.end()) from <algorithm>). Then write a recursive function that builds an arrangement: at each level, try each unused letter in order, mark it used, recurse, then unmark it. When the arrangement is as long as the word, print it.

Read one line holding a nested list of integers with no spaces, such as [1,[2,3],[[4]],-5]. The outermost list has depth 1, a list inside it has depth 2, and so on. Print:

  • Sum: <s>, the sum of all the integers
  • Weighted: <w>, the sum of each integer multiplied by the depth of the list it sits in
  • Depth: <d>, the deepest list depth

Here 1 and -5 are at depth 1, 2 and 3 at depth 2, and 4 at depth 3, so the weighted sum is 1 + (2 + 3) × 2 + 4 × 3 - 5 = 18. Lists may be empty, like [] or [1,[]].

Write a recursive parse_list(const std::string& s, std::size_t& pos, int depth) that starts at a [, reads items until the matching ], and calls itself for each inner list.

long long power(long long base, int exponent) {
    if (exponent == 0) {
        return 1;                               // base case
    }
    return base * power(base, exponent - 1);    // recursive case
}
std::string reversed(const std::string& s) {
    if (s.size() <= 1) {
        return s;
    }
    return reversed(s.substr(1)) + s[0];
}
void subsets(const std::vector<int>& items, std::size_t i, std::vector<int>& chosen) {
    if (i == items.size()) {
        print(chosen);                 // one complete choice
        return;
    }
    subsets(items, i + 1, chosen);     // choice 1: skip items[i]
    chosen.push_back(items[i]);        // choice 2: take items[i]
    subsets(items, i + 1, chosen);
    chosen.pop_back();                 // undo, so the caller sees chosen unchanged
}
Input:
cab
Output:
abc
acb
bac
bca
cab
cba
Total: 6
Input:
[1,[2,3],[[4]],-5]
Output:
Sum: 5
Weighted: 18
Depth: 3