Can someone explain how recursion works when finding all subsets?

Question

I cannot, for the life of me, picture recursion and what it's doing. I struggle with this a lot. From the Competitive Programmer's Handbook, I uncovered the following snippet of code in C++ as a solution to the following problem:

Consider the problem of generating all subsets of a set of n elements. For example, the subsets of {0,1,2} are ;, {0}, {1}, {2}, {0,1}, {0,2}, {1,2} and {0,1,2}.

An elegant way to go through all subsets of a set is to use recursion. The following function search generates the subsets of the set {0,1,...,n − 1}. The function maintains a vector subset that will contain the elements of each subset. The search begins when the function is called with parameter 0.

When the function search is called with parameter k, it decides whether to include the element k in the subset or not, and in both cases, then calls itself with parameter k + 1 However, if k = n, the function notices that all elements have been processed and a subset has been generated.

void search(int k) {
    if (k == n) {
        // process subset
    } else {
        search(k+1);
        subset.push_back(k);
        search(k+1);
        subset.pop_back();
    }
}

So sure, this function works and I have done it about 3 times by hand to see that it does work flawlessly. But why?

Short of memorizing all recursive solutions for all problems I will never be able to come up with this kind of solution. What kind of abstraction is being made here? What is the more general concept that is being used here?

I've always struggled with recursion so any help is appreciated. Thank you.

Answer 1

For each k < n we simply call search(k+1) recursively. once with the value k inside your set and once without it.

    search(k+1); // call search (k+1) with k NOT inside the set
    subset.push_back(k); // puts the value k inside the set
    search(k+1); // call search (k+1) with k inside the set
    subset.pop_back(); // removes the value k from the set

Once we reach n==k the recursion is terminated.

Imagine a binary tree of depth n, where each level represents the current value and the two branches, the decision if the value goes into your final set or not. The leaves represent all final sets.

So given n=3 and starting with k=0 you get:

search(0); 
-> search(1); // with 0 in
->-> search(2); // with 0 in AND 1 in
->->-> search (3); // with 0 in AND 1 in AND 2 in. terminates with (0,1,2)
->->-> search (3); // with 0 in AND 1 in AND 2 not in. terminates with (0,1)
->-> search(2); // with 0 in AND 1 not in
->->-> search (3); // with 0 in AND 1 not in AND 2 in. terminates with  (0,2)
->->-> search (3); // with 0 in AND 1 not in AND 2 not in. terminates with  (0)
-> search(1); // with 0 not in
->-> search(2); // with 0 not in AND 1 in
->->-> search (3); // with 0 not in AND 1 in AND 2 in. terminates with  (1,2)
->->-> search (3); // with 0 not in AND 1 in AND 2 not in. terminates with  (1)
->-> search(2); // with 0 not in AND 1 not in
->->-> search (3); // with 0 not in AND 1 not in AND 2 in. terminates with  (2)
->->-> search (3); // with 0 not in AND 1 not in AND 2 not in. terminates with  ()

As john smartly pointed out in his comment, the recursion uses the fact that:

all_subsets(a1,a2,...,an) == all_subsets(a2,...,an) U {a1, all_subsets(a2,...,an)} where U is the set union operator.

Many other mathematical definitions will translate into recursive calls naturally.