title: Can someone explain how recursion works when finding all subsets?
body: <p>I cannot, for the life of me, picture recursion and what it's doing. I struggle with this a lot. From the <em>Competitive Programmer's Handbook</em>, I uncovered the following snippet of code in C++ as a solution to the following problem:</p>
  
  <blockquote>
    <p>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}.</p>
    
    <p>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.</p>
    
    <p>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.</p>
  </blockquote>
  
  <pre class="lang-cpp prettyprint-override"><code>void search(int k) {
      if (k == n) {
          // process subset
      } else {
          search(k+1);
          subset.push_back(k);
          search(k+1);
          subset.pop_back();
      }
  }
  </code></pre>
  
  <p>So sure, this function works and I have done it about 3 times by hand to see that it does work flawlessly. But why?</p>
  
  <p>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?</p>
  
  <p>I've always struggled with recursion so any help is appreciated. Thank you.</p>