C++, lesson 11
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:
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.
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.
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'.
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.
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.
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.
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 integersWeighted: <w>, the sum of each integer multiplied by the depth of the list it sits inDepth: <d>, the deepest list depthHere 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: 6Input:
[1,[2,3],[[4]],-5]
Output:
Sum: 5
Weighted: 18
Depth: 3