1

In a book I encountered following question:

Given N step stair, in how many number of ways can you climb if you use either 1, 2 or 3 steps at a time?

Following is the code that book has given:

 int countWays(int n){

    if(n<0)
        return 0;

    if(n == 0)
        return 1;

    else return countWays(n-1) + countWays(n-2) + countWays(n-3);
  }

I have the following concerns in understanding this code:

  1. I do not understand why 1 is being returned for n=0. If there are 0 steps then obviously we do not have to climb any and 0 should be returned.

  2. For n=3 function returns 4 but i can see only 3 cases i.e. (1,1,1), (1,2), (3).

Asclepius
  • 57,944
  • 17
  • 167
  • 143
Sensiblewings47
  • 558
  • 1
  • 5
  • 16
  • 1
    2) You could climb 2 then climb 1. –  Mar 10 '13 at 02:09
  • And what about returning 1 for n==0? – Sensiblewings47 Mar 10 '13 at 02:11
  • I'm curious, is there an explicit form of this recursion? Looks horribly inefficient. I no more remember how to transform recursive functions to explicit forms. – G. Bach Mar 10 '13 at 02:14
  • 1
    There's one way of climbing a non-existent stair: `()`. – FelipeAls Mar 10 '13 at 02:14
  • 1
    @DeepeshM It is cracking the coding interview. – user1772643 Apr 15 '15 at 18:41
  • I still do not understand the logic behind the recursive function how f(n) = f(n-1)+f(n-2)+f(n-3). Can someone explain me in words?? – user1772643 Apr 15 '15 at 18:41
  • @user1772643 It's because for any random step n, given n>3, you could've arrived at it directly from any of the preceding three steps only. For example, you could've arrived at step 9 directly from steps 6, 7, or 8 only. Similarly, you could arrive at step 17 directly from steps 14, 15, and 16 only. Moreover, this pattern recurses until you reach steps 1, 2, or 3. – Asclepius Dec 05 '16 at 20:11

3 Answers3

2

I do not understand why 1 is being returned for n=0. If there are 0 steps then obviously we do not have to climb any and 0 should be returned.

When there are no steps you just go through without climbing, which is the one and only one way. As is pointed out in one of the comments, it can be represented as ().

For n=3 function returns 4 but i can see only 3 cases i.e. (1,1,1), (1,2), (3).

There are actually 4 cases: (1,1,1), (1,2), (2,1), (3).

Terry Li
  • 16,870
  • 30
  • 89
  • 134
0

As Geobits said there is four ways to climb 3 stairs

(1,1,1),(1,2),(2,1),(3)

As for why it returns 1 when n==0, this is because whenever n==0 that means that you have found exactly 1 way to climb the stairs.

Lastly this algorithm will take a very long time if you put any high number in, if you are looking for a dynamic programming approach you should create a n sized array and initialize the first three entries as 1,2,4 and then iterate through the array starting and index 3, each time set the index to array[i-1] + array[i-2] + array[i-3]. This will do the minimal amount of computation but will use a huge amount of memory.

There is a better way where you only use a 1x3 sized array, but I will leave how to do that as an exercise for the user.

Asclepius
  • 57,944
  • 17
  • 167
  • 143
placeybordeaux
  • 2,138
  • 1
  • 20
  • 42
  • 1
    I still do not understand returning 1 for n=0. n=0 means that you do not have any more stairs to climb then how still 1 way is there to climb? – Sensiblewings47 Mar 10 '13 at 03:05
  • It is not saying that there is another way to climb, it is saying that it found exactly one way to climb the stairs. – placeybordeaux Mar 10 '13 at 03:10
  • @placeybordeaux Your comment above is just restating the question. It is not an answer or an explanation. – Asclepius Dec 05 '16 at 19:29
0

I do not understand why 1 is being returned for n=0. If there are 0 steps then obviously we do not have to climb any and 0 should be returned.

To complement the answer by Terry, the general answer to the problem is the tribonacci(n+2) sequence. Accordingly, for n=0, i.e. tribonacci(2), the value is 1. This is just a computational hack for the stairs problem, one that works. For a more thorough investigation, please see this answer.

You can certainly choose to reject f(n=0) = 1. If you do, you can then just use the following base case values which you will be more comfortable with. All n>3 will be recursed to these base cases.

  • f(n=1) = 1
  • f(n=2) = 2
  • f(n=3) = 4
Asclepius
  • 57,944
  • 17
  • 167
  • 143