I don’t understand the logic why this C ++ recursion function works

Question

This function is designed to generate the number of combinations of large and short steps up the stairs (a value specified by the user). The short step includes 1 step, and the large step 2 steps.

However, I do not understand the recursive insight used here. I am very grateful for the explanation of why this gives rise to the number of necessary combinations. Working with him, I see that it works, but I'm not sure how I myself would come to this logic.

Can anyone 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);

    }
}

Answer 1

To go down numStairs, you can:

• , (numStairs - SMALL_STEP);
• , (numStairs - LARGE_STEP).

, - (numStairs - SMALL_STEP) (numStairs - LARGE_STEP), , .

, , (S), , (SS L) , (SSS, SL LS), , , .

. , , .

Answer 2

. . numStars < 4, :

ss=small step (1)
ls=large step (2)
1 step-{{ss}}==1
2 steps-{{ss,ss},{ls}}==2
3 steps-{{ss,ss,ss},{ls,ss},{ss,ls}}==3

, . , , . , numStars-LARGE_STEP, . , numStais-SMALL_STEP.

, [n] = [n-1] + [n-2].

, . . .

int* num_combinations = new int[num_stairs];
for (int i = 0; i < 4; i++) num_combinations[i]=i;
for (int i = 4; i < num_stairs; i++) num_combinations[i]=num_combinations[i-1]+num_combinations[i-2];
int ret = num_combinations[num_stairs-1]+num_combinations[num_stairs-2]
delete[] num_conbinations;
return ret;

O(n) vs O (n ^ 2)

Answer 3

:

, N 1 thru N.

:

• .

, .

, K.

K+1, K+2.

, , , :

• K+1 N
• K+2 N

, , :

• N-(K+1)
• N-(K+2)

---

, :

int CountWays(int numStairs)
{
    if (numStairs < 4)
        return numStairs;
    // If there is  1 step , then there is  1 combination  to climb it   up
    // If there are 2 steps, then there are 2 combinations to climb them up
    // If there are 3 steps, then there are 3 combinations to climb them up

    int x = CountWays(numStairs - SMALL_STEP);
    // The number of different combinations to climb up
    // from the bottom of the staircase to step N-(K+1)

    int y = CountWays(numStairs - LARGE_STEP);
    // The number of different combinations to climb up
    // from the bottom of the staircase to step N-(K+2)

    return x+y;
}

, , 1, 2, 3, 5, 8, 13,...

, ( ):

int CountWays(int numStairs)
{
    int prev = 0;
    int curr = 1;
    for (int i=0; i<numStairs; i++)
    {
        int next = prev+curr;
        prev = curr;
        curr = next;
    }
    return prev;
}

Answer 4

, . , :
- - .
- - .
- , , , , .
.
, , , . " " - : ( , ).
, .

Answer 5

f (n) - n- ( 0).

stair n, n-1 n-2.
n-1, n-2 th n-3, .

- , f(-1), f(-2),... f(- infinity)... stopping condition: stair 1, 1, .. stair 0 stair 1.

stair 2, 2 ways: stair 0 + 2 stair 1 + 1.

f(1) = 1  
f(2) = 2  
f(3) = 3  
f(n) = f(n-1) + f(n-2) // n>3

Answer 6

One thing that particularly confuses this recursion is that it is parameterized in terms of constants SMALL_STEPand LARGE_STEP, but the termination condition ( if (numsteps < 4)) is true only for specific values SMALL_STEP = 1and LARGE_STEP = 2- if you change any of these parameters, the code will be incorrect. Perhaps the code should be:

int CountWays(int numStairs) {
    if (numStairs < 0) {
        return 0;
    } else if (numStairs == 0) {
        return 1;
    } else {
        return CountWays(numStairs - SMALL_STEP) + CountWays(numStairs - LARGE_STEP);
    }
}

This is slightly less efficient (it takes several additional iterations to get the answer), but still has the same asymptotic complexity - O (2 ⁿ )