Staircase Problem - understanding the basic logic

user_10067128 0
Viewed 338

Here is the recursive version of the staircase problem (There are N stairs, a person standing at the bottom wants to reach the top. The person can climb either 1 stair, 2 stairs or 3 stairs at a time. Count the number of different ways the person can reach the top.)

public static int findStep(int n) 
    { 
        if (n == 1 || n == 0)  
            return 1; 
        else if (n == 2)  
            return 2; 

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

My question is, why we are returning 1 when n=0 ??

To me, n=0 means there are no more stairs so it should return 0, but if I do so then the program doesn't work for other non-zero inputs. I saw similar questions in this site but non of those explain why we are returning 1 when there are no more stairs.

recursion algorithm java
3 Answers

This is a selection problem. Think of the recurrence as the number of ways to select and order a combination of zero or more 1's, zero or more 2's, and zero or more 3's, that will together sum to n. There is only one way to make such a selection for n = 0: select none.

user_20347870

In this code n=0 means in the last step n was equal to 1or 2 or 3. in other words :

n-1=0 which means in the last step n=1, so there is one way to reach the top of stairs.

n-3=0 which means in the last step n=3, so one way to reach the top of stairs is to make 3 steps.

user_37005240
user_108195730
Related