Finding number of possible combinations with recursion.

[Scorpio588]

Hello! I'm pretty new to programming, and I'm trying to understand how I would write a recursive function that counts the possible combinations of steps one might take if they have the choice of taking 1 or 2 steps at a time. I'd like the only argument to be the number of steps they would climb. I think I understand what the base case should be, but that's about it (I did find another thread discussing something similar, posted a couple years ago, but I had a hard time understanding it). Any clues or other help would be much appreciated! Thank you!

int CountWays(int steps)
{
     if (steps == 0)
     {
          return 0;
     }
     else
     {
      ?
     }
}

If there's some way to do this without adding more arguments, that's what I'm looking for.

[Scorpio588]

Example:

If you're climbing 4 steps then the possible combinations can be: (1,1,1,1) (1,1,2) (1,2,1) (2,1,1) (2,2)

So inputting "4" into CountWays should return a 5.

[cire]

steps == 0 is a base case which you should handle, however it is not the only one.

[D80DSL3A]

I'm not sure my solution is correct, but it's agreeing with the # of ways for the cases of 4,5,6 or 7 stairs as enumerated by hand.
The counts I get by hand are:
n ways
4 5
5 8
6 13
7 21
My base case: If( n < 3 ) return n;
Reason is this covers the cases for either 0, 1 or 2 stairs, which = n.
For 3 or more stairs, the # of ways = #ways if n-1 stairs are left + #ways if n-2 stairs are left.

Not sure how to explain any further without showing my code, except to say it's just 2 lines.
EDIT: Removed my code.
Did not see cires' post.

[Scorpio588]

Thank you!

So I started doing the math by hand for the outcomes I wanted and realized the sequence is just an offset of the Fibonacci sequence.

Fibonacci:
position: 1 2 3 4 5 6 7 8 9 10
output: 1 1 2 3 5 8 13 21 34 55

My Desired Algorithm:
Position: 1 2 3 4 5 6 7 8 9 10
output: 1 2 3 5 8 13 21 34 55 89

The Fibonacci code I've used is:

int CountWays(steps)
{
     if(steps <= 0)
     {
          return 0;
     }

     else if (steps == 1)
     {
           return 1;
     }

     else 
     {
          return CountWays(steps - 1) + Countways(steps - 2);
     }
}

Any advice on how I might I offset the sequence?

[D80DSL3A]

I have seen 2 different ways to seed the Fibonnaci sequence. Either 0, 1 or 1, 1
ie. F(0) = 0 or F(0)=1
The 1st seed method gives the desired sequence.
BTW you missed the F(6)=8 and F(5)=8 cases in your listings.

[Scorpio588]

Thanks for the correction, I fixed it.

Seeding with 0, 1 would offset it in the opposite direction I'd like to. And I'm not sure how I would change the seed anyway. I would want to seed the sequence with 1, 2 somehow if that's the way to go about this.

EDIT: OK, never mind about me not knowing how to seed it. When I seed it with 1, 2 I get results one offset too far. 4 comes out 8, 5 comes out 13 etc.

EDIT: THANK YOU, THANK YOU, THANK YOU! Seeding it with 1, 1 is exactly what I wanted! I just corrected this:

if (steps <= 0)
{
     return 1;
}

and it works exactly the way I wanted it to!

[D80DSL3A]

You're welcome. I didn't see the Fibonnaci connection and struggled myself.
I got this and it seems to work:

int steps(int n)
{
    if(n<3) return n;
    return steps(n-1) + steps(n-2);
}

EDIT: Actually, neither seed method seems to work quite right. We want S(0)=0, S(1)=1 and S(2)=2 != S(0) + S(1)

So it appears that the Fib sequence behavior doesn't start until n=3.

[Scorpio588]

This seems to work just the way I want it to, except for when steps = 0. Then it returns 1. Other than that, every other number seems to work like it should.

int CountWays(steps)
{
     if(steps <= 0)
     {
          return 1;
     }

     else if (steps == 1)
     {
           return 1;
     }

     else 
     {
          return CountWays(steps - 1) + Countways(steps - 2);
     }
}

[D80DSL3A]

See my post above your last.

[Scorpio588]

I read it, I guess I'm just confused as to what you mean by "!= S(0) + S(1)" In my program S(2) = 2, S(1) = 1, and S(0) = 1. Every input above 0 works like I want it to.

[D80DSL3A]

We have a case which doesn't match the Fib sequence either way we seed it.
We require:
CountWays(0) = 0
CountWays(1) = 1
CountWays(2) = 2
No Fib sequence is 0, 1, 2,... because 2 != 0 + 1

The reason for my base case is that it works for these first 3 cases whereas no fib sequence does.
Does that make any better sense?