Recursion problem

[leeba]

I am trying to figure out how many ways you can go if you only take one or two steps. For example. If the number is 4 there are 5 ways you can move going one or two steps.
I have to do it with recursion.
I have the following code:

public class Ex16
{
    public static int numWaysToClimb(int n)
    {
     if (n==0)
        return 0;
     if (n==1)
        return 1;
     return numWaysToClimb(n-1,n-2);
    }
    public static int numWaysToClimb(int x, int y)
    {
        if ((x==0)||(y==0))
            return 0;
        if ((x==1)||(y==1))
            return 1;
        return (numWaysToClimb(x-1,y-2)+numWaysToClimb(x-2,y-1));
    }
}

When I give it 4 it answers me two. I am guessing my problem is in the base cases in the second method.

Any help will be appreciated.

[BestJewSinceJC]

4-5
4-5-6
4-3
4-3-2

I count 4 ways. And the number you start at will never matter if I'm doing this correctly, so whats the point? If I'm not doing it correctly than perhaps you should explain.

[leeba]

Sorry I didn't explain well enough.
I should say it as going down a ladder or steps. If you are on step 4 and are going down one or two steps at a time there are 5 ways to do it.
1-1-1-1
2-2
2-1-1
1-2-1
1-1-2

I have since corrected (and it works closer to the right way but not totally) the code to:

public static int numWaysToClimb(int n)
    {
     if (n<=1)
        return 1;
     return numWaysToClimb(n,n);
    }
    public static int numWaysToClimb(int x, int y)
    {
                System.out.println(x + " " + y);
       if ((x==0)||(y==0))
            return 1;
       else if ((x==1) || (y==1))
                return 1;
       else
            return (numWaysToClimb(x-1,y-2)+numWaysToClimb(x-2,y-1));
    }

Thank you for your help.

[BestJewSinceJC]

Ok, well why do you need your method to take two parameters? If you're always taking one or two steps, the only parameter you should need is the step you're currently on. Then, at the end of the method, you should have two recursive calls (which you do). The one should try to go down two steps, the other should try to go down one step. If you cannot go down anymore, then you should return 0 for that attempt.

[BestJewSinceJC]

Sorry.. you'd actually also need a second int parameter to count the total number of ways

[leeba]

Sorry I didn't explain well enough.
I should say it as going down a ladder or steps. If you are on step 4 and are going down one or two steps at a time there are 5 ways to do it.
1-1-1-1
2-2
2-1-1
1-2-1
1-1-2

I have since corrected (and it works closer to the right way but not totally) the code to:

public static int numWaysToClimb(int n)
    {
     if (n<=1)
        return 1;
     return numWaysToClimb(n,n);
    }
    public static int numWaysToClimb(int x, int y)
    {
                System.out.println(x + " " + y);
       if ((x==0)||(y==0))
            return 1;
       else if ((x==1) || (y==1))
                return 1;
       else
            return (numWaysToClimb(x-1,y-2)+numWaysToClimb(x-2,y-1));
    }

Thank you for your help.

[leeba]

Sorry I didn't see that it was really posted my answer before. I wil try what you guys saud and let you know.

[BestJewSinceJC]

if ((x==0)||(y==0))
            return 1;
       else if ((x==1) || (y==1))
                return 1;

One problem lies in the 'else if' part of that code. If you're on the first step, you still have to go down one. That makes a total of two ways. However, since you said 'return 1', you only account for one of the ways, and prevent the recursive call. (Basically, remove the else if portion, I think your code will work better).. you have two base cases where you should only have one.

Also, in your recursive call, why are you subtracting from both x and y? What do x and y represent? I'm assuming x represents the step you're currently on. If so, what does y represent? And finally, I retract what I said previously about needing a parameter to count the total number of ways. That's already taken care of by "return (numWaysToClimb(x-1,y-2)+numWaysToClimb(x-2,y-1));" (Well, it will be once your code works properly)

Also - I apologize for the conflicting advice (about the second parameter). I'm almost positive what I said in this post is correct. When I get to work in a couple hours, I'll code the solution myself to make sure that it is, in fact, good advice. I'm not going to post the solution because that would destroy the point of learning, but I will give you some hints from there if you need it.

[leeba]

I got it to work without the overloading as you said.
Thank you

[BestJewSinceJC]

edit: nvmmm