CODEWITHSUNDEEP
c++recursion
user1697083
user1697083

Reputation:

Don't understand logic behind why this C++ recursion function works

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

    }
}

Upvotes: 4

Views: 1017

Answers (6)

Chris Dodd
Chris Dodd

Reputation: 126378

One thing that is particularly confusing about this recursion is the fact that it is parameterized in terms of the constants SMALL_STEP and LARGE_STEP, but the termination condition (if (numsteps < 4)) is only correct for the specific values of SMALL_STEP = 1 and LARGE_STEP = 2 -- if you change either of those, the code is incorrect. Arguably 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 marginally less efficient (requires a couple of extra iterations to get the answer) but still has the same asymptotic complexity -- O(2n)

Upvotes: 0

barak manos
barak manos

Reputation: 30136

Here is the recursion-logic in this case:

Suppose you have N steps numbered 1 thru N.

At any point, you can choose one of two options:

  1. Climb one step
  2. Climb two steps

You want to calculate the number of different combinations to climb up the staircase.

Now, let's say you're currently standing on step K.

You can choose to climb either to step K+1 or to step K+2.

So all you need to do is add:

  • The number of different combinations to climb from step K+1 to step N
  • The number of different combinations to climb from step K+2 to step N

Or equivalently, you can add:

  • The number of different combinations to climb from the bottom of the staircase to step N-(K+1)
  • The number of different combinations to climb from the bottom of the staircase to step N-(K+2)

Having said that, here is how the recursive function works:

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;
}

You may have noticed that this function simply yields the Fibonacci Sequence 1, 2, 3, 5, 8, 13, ...

BTW, an iterative implementation would be much more efficient in this case (as in many other cases):

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;
}

Upvotes: 1

IdeaHat
IdeaHat

Reputation: 7881

Well Lets think of it this way. I have a number of stairs n left. If numStars < 4, than the number of combinations is always numstairs:

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

Bigger than that, it may get more complicated. But if I have n left, i can take Either a big step, or a small step. If I take a big step, than there will be numStars-LARGE_STEP steps left, so I just need to find the total number of combinations of that many steps. If I take a small step, than I just need to find the total number of combinations of numStais-SMALL_STEP.

Put in the terms of a recursion, combinations[n]=combinations[n-1]+combinations[n-2].

It should be noted that this is not the fastest way to do this by any means. This redoes a ton of work for each iteration. A dynamic programming approach would be much preferable.

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)

Upvotes: 1

Aseem Goyal
Aseem Goyal

Reputation: 2723

let f(n) be the number of ways to reach nth stair from starting (stair number 0) .

To reach stair n , you 1st have to reach start n-1 or n-2 .
similarly to reach stair n-1 , you need to reach n-2 th or n-3 th stair , and recursion goes like this ....

But it has to stop somewhere otherwise you keep on evaluating f(-1) , f(-2) , ... f(- infinity) ... so there is the stopping condition : to reach stair 1 , you can ONLY do so in 1 step i.e from stair 0 to stair 1 directly .

To reach stair 2 , 2 ways : stair 0 + step of 2 , or stair 1 + step of 1 .

Therefore 

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

Upvotes: 0

Mike Seymour
Mike Seymour

Reputation: 254631

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.

Upvotes: 6

maddin45
maddin45

Reputation: 747

The code tries to decompose the problem by making it smaller in every step. If there are less than four steps to go , the number of possible combination is equal to the number of stairs:
- For one stair the only possible combination is a small step.
- For two stairs the possible combinations are a large step or two small steps.
- For three stairs you can go either three small steps, a small step and a large step or a large step and a small step.
These cases will end the recursion.
For every other number of stairs you can go either a small step and then the rest of the stairs, or a large step and then the rest of the stairs. The "rest of the stairs" is where the recursion happens: It will just calculate the number of possibilities for the reduced number of stairs (one or two steps less, depending on size of the first step).
Add them all together and you get the total number of combinations for walking up the stairs.

Upvotes: 0

Related Questions