Don't understand logic behind why this C++ recursion function works
c++, recursion
Solution
To go down `numStairs`, you can either:
- take a small step, then go down `(numStairs - SMALL_STEP)`; or
- take a large step, then go down `(numStairs - LARGE_STEP)`.
So the total number of ways is the sum of the number of ways to go down `(numStairs - SMALL_STEP)` and the number of ways to go down `(numStairs - LARGE_STEP)`, hence the recursion.
It's simple enough to see that there's one way to go down one step (S), two to go down two (SS or L) and three to go down three (SSS, SL or LS), hence the termination condition.
You might recognise this recursion as the definition of the Fibonacci sequence. For bonus points, you might like to restructure the calculation so that it runs in linear, rather than exponential, time.
Problem
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. 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 I am not sure how I would have arrived at this logic myself. Would it be possible for someone to shed some light on this? Here is the code: ``` int CountWays(int numStairs); int combination_strides = 0; const int LARGE_STEP = 2; const int SMALL_STEP = 1; int main() { cout << "Enter the number of stairs you wish to climb: "; int response = GetInteger(); int combinations = CountWays(response); cout << "The number of stride combinations is: " << combinations << endl; return 0; } int CountWays(int numStairs) { if (numStairs < 4) { return numStairs; } else { return CountWays(numStairs - SMALL_STEP) + CountWays(numStairs - LARGE_STEP); } } ```