Backtracking N stairs question getting 0 cases Java

Question

N Stairs question is to compute the number of distinct ways to reach the top. Each time you can either climb 1 or 2 steps. For example, if the input is 3, the desired output is 3 (1+1+1,1+2,2+1).

I am learning backtracking in Java, so I want to implement it in this question, although DP would work better in such a case. I view it as a practice if I understand backtracking well, but apparently not. I got stuck because my algorithm gives me a 0 output for every case. Below is my code:

    public int climbStairs(int n) {
        int cnt=0,k=0;
        climb(cnt,k,n);
        return cnt;
    }
    public void climb(int cnt, int k, int n){
        if(k==n){
            cnt++;
            return; 
        }
        for(int i=1;i<3;++i){
            if(k<n){
                k+=i;
                climb(cnt,k,n);
                k-=i;
            }
        }
    }

Could you help me figure out what's wrong with my code? I tried debugging it, and I noticed every time it returns, cnt will automatically change to 0, but I just can't figure out why.

Thank you so much in advance!

Edited version:

public class ClimbStairs {
    public static void main(String[] args) {
        System.out.println(climbStairs(3));
    }
    public static int climbStairs(int n) {
        int cnt=0,k=0;
        return climb(cnt, k, n);
    }
    public static int climb(int cnt, int k, int n){
        if(k==n){
            cnt++;
        }
        for(int i=1;i<3;++i){
            if(k<n){
                k+=i;
                climb(cnt,k,n);
                k-=i;
            }
        }
        return cnt;
    }
}

Answer 1

Every recursive implementation consists of two parts:

• base case - a situation (or situations) that represent the edge-case for which the result is already known. For this problem, if we choose to track the number of steps (going forward I'd say that it's not mandatory) then the base case is when the number of stairs is equal to the number of steps, i.e. k == n. And if we don't track the number of steps then the base case will be represented with two edge-cases: there are no stairs at all - no steps required and there's only one way to take zero steps, so the output is 1, and the second is when we have only one stair then we have to take one step and the output is also 1.
• recursive case - is the part where recursive calls a made and where main logic resides.

We have two possible branches in the recursive case for every k < n: we can either take 1 step or 2 steps. And therefore we have to make two recursive calls that represent these situations. All these calls can be represented graphically as a tree. To understand the logic better can you drow this tree of method-calls starting from the first one that is made inside the climbStairs() and track the value of k for each call. Until the condition k < n is meat each vertex will spawn two branches. When k is greater or equal to n the call hits the base case. And starting from the bottom to the top you can figure out what are the return values for each call.

Also, note that instead of being void your method must return the number of paths that are found. And the third parameter that represents this number is redundant.

public static void main(String[] args) {
    System.out.println(climbStairs(1));
    System.out.println(climbStairs(3));
}

public static int climbStairs(int n) {
    if (n < 0) { // cut off the incorrect input
        return 0;
    }
    return climb(n, 0);
}

public static int climb(int n, int k){
    if (k > n) { // an invalid situation
        return 0;
    }
    if (k == n) { // a path was found
        return 1;
    }
    // there are two alternative branches for every k < n
    int count = 0;
    count += climb(n, k + 1); // move one step forward
    count += climb(n, k + 2); // move two steps forward
    return count;
}

As I said above tracking the number of steps isn't required. Instead, we can reduce the number of stairs while making recursive calls. And that will allow us to place all logic in a single method. Like that:

public static int climbStairs(int n) {
    if (n < 0) { // cut off the incorrect input
        return 0;
    }
    if (n == 0) { // a base case when we have NO stairs - we have to take zero steps (there's only ONE way to do that)
        return 1;
    }
    if (n == 1) { // a base case when we have only one stair - we have to take one step (there's only ONE way to do that)
        return 1;
    }
    // there are two alternative branches for every n > 1
    int count = 0;
    count += climbStairs(n - 1); // move one step forward
    count += climbStairs(n - 2); // move two steps forward
    return count;
}

Output

1
3