Finding number of possible combinations with recursion.

Feb 25, 2015 at 10:23pm
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!

1
2
3
4
5
6
7
8
9
10
11
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.
Last edited on Feb 25, 2015 at 10:41pm
Feb 25, 2015 at 10:36pm
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.
Last edited on Feb 25, 2015 at 10:38pm
Feb 26, 2015 at 12:36am
steps == 0 is a base case which you should handle, however it is not the only one.
Last edited on Feb 26, 2015 at 12:36am
Feb 26, 2015 at 12:41am
closed account (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.
Last edited on Feb 26, 2015 at 12:57am
Feb 26, 2015 at 1:10am
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:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
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?
Last edited on Feb 26, 2015 at 1:25am
Feb 26, 2015 at 1:22am
closed account (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.
Last edited on Feb 26, 2015 at 1:28am
Feb 26, 2015 at 1:27am
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:
1
2
3
4
if (steps <= 0)
{
     return 1;
}


and it works exactly the way I wanted it to!
Last edited on Feb 26, 2015 at 1:36am
Feb 26, 2015 at 1:53am
closed account (D80DSL3A)
You're welcome. I didn't see the Fibonnaci connection and struggled myself.
I got this and it seems to work:
1
2
3
4
5
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.
Last edited on Feb 26, 2015 at 1:58am
Feb 26, 2015 at 2:21am
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.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int CountWays(steps)
{
     if(steps <= 0)
     {
          return 1;
     }

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

     else 
     {
          return CountWays(steps - 1) + Countways(steps - 2);
     }
}
Last edited on Feb 26, 2015 at 2:21am
Feb 26, 2015 at 2:32am
closed account (D80DSL3A)
See my post above your last.
Feb 26, 2015 at 2:54am
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.
Feb 26, 2015 at 3:04am
closed account (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?
Last edited on Feb 26, 2015 at 3:07am
Topic archived. No new replies allowed.