Hunter Liu's Website

20. Week 10 Thursday: Recursion!

Since we didn’t actually finish coding up Connect Four last discussion, I may spend some time tying up loose ends (e.g. with input validation).

But at the same time, I think it’s important to be exposed to the magic of recursion. I think this is one of the most elegant (though typically inefficient) ways to solve certain types of problems with computer programming; we in particular see recursion frequently in things like sorting algorithms, where divide-and-conquer strategies help simplify the problem at hand.

Recursive functions are simply functions that call themselves. For instance,

1void recursive_print() {
2    cout << "Hello world!" << endl; 
3    recursive_print(); 
4} 

This function prints “Hello world!” to the screen, then calls itself. This causes C++ to print “Hello world!” to the screen again, but then the function is called yet again! This continues until either your computer runs out of battery or it runs out of memory.

The fact that a single call to recursive_print eventually causes the program to crash is interesting in and of itself. Every time you call a function, your computer needs to set aside some memory for that function to do its thing; this memory is freed up once the function ends. But in this case, we just keep calling more and more functions, causing our computer to set aside more and more memory until there’s no more memory left to give. This is the famous stack overflow error, and it’s an example of a runtime error.

Thus, in order for any recursive function to be actually usable, it needs to end at some point. This is similar to how infinite loops are (generally) quite useless.

An example of an actually useful recursive function is the following, which computes the \(n\)-th Fibonacci number:

 1int fibonacci(int n) {
 2    // the 0th fibonacci number is 0, 
 3    // the 1st is 1, and the 2nd is 1. 
 4    if(n == 0) {
 5        return 0; 
 6    } else if(n == 1 || n == 2) {
 7        return 1; 
 8    } 
 9
10    // otherwise, the n-th fibonacci number is the sum 
11    // of the two that came before it. 
12    return fibonacci(n - 1) + fibonacci(n - 2); 
13} 

This is perhaps a rather standard example, but it highlight a general structure of recursive functions: they first check for a “base case” — this corresponds to \(n = 0, 1, 2\), in which case computing the \(n\)-th Fibonacci number is easy — followed by a “recursive step”, where we inch our way towards the easier base case.

Let’s give a nontrivial example of when recursion makes a problem much easier.

For instance, if vec = {9, 3, 7, 2} and target = 10, we should return true, since 3 + 7 = 10. However, with the same vec and target = 1, we should return false, since no set of elements from vec add up to exactly 1.

This is nearly impossible with one or more loops, in my opinion. I want to say “for every subset of vec…”, but I don’t really know how to write this in C++.

Instead, we can make the clever observation that every subset of vec either contains 2 (the last element) or it doesn’t. Thus, I can look at all the subsets of only the first three elements — {9, 3, 7} — and determine if any of them add up to 10 or if they add up to 8. This corresponds to including 2 in this subset or not including 2.

But this is exactly what the subset_sum function purports to do, and this observation now reduces the length of my vector by one, i.e. it makes the problem easier to solve! Better yet, when there’s exactly one element in vec, the problem is extremely easy to solve. Thus, we may write the following pseudocode:

1. If vec contains exactly one element, check if it’s equal to target and return true or false accordingly.
2. Declare an integer last equal to the last element of vec, then remove it from vec.
3. Call subset_sum recursively to determine if the shorter vec has a subset whose elements add to target.
4. Call sumset_sum recursively to determine if the shorter vec has a subset whose elements add to target - last.
5. Return true if either result from steps 3 or 4 was true; return false otherwise.

In code, we may combine steps 3-5 into a single line, yielding the following elegant solution:

 1bool subset_sum(vector<int> vec, int target) {
 2    if(vec.size() == 1) {
 3        return vec.at(0) == target; 
 4    } 
 5
 6    int last = target.at(target.size() - 1); 
 7    vec.pop_back(); 
 8
 9    return subset_sum(vec, target) || 
10           subset_sum(vec, target - last); 
11} 

Think carefully about the logic of this recursive function, and think about if it’s even possible to express this algorithm without recursion!