title: Don't understand logic behind why this C++ recursion function works
body: <p>This function is designed to generate the number of combinations of large and short strides up a staircase (a value that is given by the user). A short stride involves 1 step, and a large stride involves 2 steps.</p>
  
  <p>However, I don't understand the recursive insight used here. I'd really appreciate an explanation of why this generates the number of combinations required. Working through it, I can see it works, but <strong>I am not sure how I would have arrived at this logic myself.</strong></p>
  
  <p>Would it be possible for someone to shed some light on this? </p>
  
  <p>Here is the code: </p>
  
  <pre><code>int CountWays(int numStairs);
  int combination_strides = 0;
  const int LARGE_STEP = 2;
  const int SMALL_STEP = 1;
  
  int main() {
  
      cout &lt;&lt; "Enter the number of stairs you wish to climb: ";
      int response = GetInteger();
      int combinations = CountWays(response);
      cout &lt;&lt; "The number of stride combinations is: " &lt;&lt; combinations &lt;&lt; endl;
  
      return 0;
  }
  
  
  int CountWays(int numStairs) {
  
      if (numStairs &lt; 4) {
      return numStairs;
  
      } else {
      return CountWays(numStairs - SMALL_STEP) + CountWays(numStairs - LARGE_STEP);
  
      }
  }
  </code></pre>