Recursion math problem

[MacemanD]

 

Create a class with a method that calls itself to calculate the number of ways a person could climb a staircase of n steps if they can take 1 step at a time, 3 steps at a time, 5 steps at a time, or any combination thereof. Allow the user to specifiy the number of steps n. Assume at the top of the stairs there is a flat surface so it doesn't matter if the user oversteps on their last step.

 

I can think of how to do this if I were to set up while()s inside of while()s infinitely, but I don't know how to set it up in a recursive manner. I understand what recursion is, but I don't know what algorithm should be used for this problem.

Any help is appreciated.

[Argi]

Take the problem one step (pun intended) at a time.  You have an n step staircase, and you're taking 1 step at a time.  Therefore it will take n steps to get to the top.

 

There's also a hint in "Assume at the top of the stairs there is a flat surface so it doesn't matter if the user oversteps on their last step."

[Andre S. Veteran]

Recursion is iteration where the state of each iteration lives on the call stack. So if you can devise a simple iterative algorithm for this, it shouldn't be too difficult to translate it to a recursive style. So I would say start by figuring it out iteratively and translate it after. Infinitely nested while loops certainly doesn't sound  like a viable solution.

[Seahorsepip Veteran]

What about for loops?

For x<n/1

For y<n/3

For y<n/5

If 1*x+3*y+5*z > n {

echo x y z

}

Havent actually tried the code but it should work I suppose. Not sure if it might goes a bit above the stairs but that could be solved by stopping each loop when a result has been found so stopping z first then y and then x if I'm correct.

It should look in the following order for n = 20

x y z

0 0 1

0 0 2

0 0 3

0 0 4

0 1 0

0 1 1

0 1 2

Etc..

Ofcourse this is a iteration not a recursion, but if you look at each for loop you see that it's 3 times the same so all the for loops could be made each into a function which happens to be the same all the same and the same as the main function.

Though I admit this math problem is harder then it looks.

[Seahorsepip Veteran]

function stairs(n) {
    for(x=0;x<=n;x++) {
        for(y=0;y<=n;y++) {
            for(z=0;z<=n;z++) {
                if(x*5+y*3+z*1 >= n) {
                    console.log(x+"*5 "+y+"*3 "+z+"*1");
                    z = n+1;
                }
            }
            if(x*5+y*3 >= n) {
                y = n+1;
            }
        }
        if(x*5 >= n) {
            x = n+1;
        }        
    }
}

Since I was bored I wrote a for loop in js, this is not recursive but a iteration, if you look at the way the function works you can see that it can be made recursive.

[MacemanD]

Thanks for the attempt at it. This is partially working, but it is missing some of the possibilites.

 

For example, with 2 steps it only counts 3 possiblities:

0*5 0*3 2*1
0*5 1*3 0*1
1*5 0*3 0*1

 

When in fact, we can also do these 2:

1*1 1*3 0*5

1*1 0*3 1*5

 

And, when there is only 1 step, there should be 3 possiblities. As we can do 1, 3, or 5 steps (because we can overstep the top).

 

I played around with your code for a bit, but I couldn't ever get it to return the correct values. This is hard one.

[Andre S. Veteran]

It's not that difficult. I coded a solution in 5 minutes but since this is homework I'm not going to just give it to you but I'll give you some hints. :)

 

First consider that this is a sum. It's a function that returns an integer representing the sum of something (i.e. the possibilities). So if you're doing this iteratively you're mutating an integer representing the running total, if you're doing this recursively you're using return values to accumulate the result.

 

Then think about what you're doing each iteration/recursive call. If you're at the top of the stairs, you've just found one more way to climb the stairs. If not, you can either advance by 1, 3 or 5 (and you need to sum the results of all 3 possibilities). There are only these two possibilities. So your function is basically just an if/else statement.

 

Also, try to do it recursively. It's much harder to solve this iteratively. I wrote an iterative version and the simplest way I could figure was to use a stack data structure to emulate the stack of functions I had with the recursive version.

[MacemanD]

I coded a solution in 5 minutes but since this is homework I'm not going to just give it to you but I'll give you some hints. :)

 

I understand this, but for the life of me I just can't do it. I have restarted from scratch about 5 times. Below is what I have on my latest version. What more can you give me without giving me everything?

	int answer = 0;
	int step;
	
	public int check(int steps, int increment){
		
		answer++;
		step=0;
		while(step<steps){
			step=step+increment;
		
			if(step<steps){
				check(steps,1);
				//check(steps,3);
				//check(steps,5);
			}
		}
			
		return answer;
	}

[Andre S. Veteran]

You don't need the outer mutable variable "answer" and you don't need the while loop. The looping is accomplished by the function calling itself, and the answer is the return value of the function. You have the right intuition that the function needs to call itself three times per iteration, i.e. for possibilities 1, 3 and 5 (admitedly you could use a for loop for this but otherwise this function should contain no explicit loop). You're missing one parameter on the function to know where you're at in the staircase.

[MacemanD]

Don't I want to keep track of the answer by ++ing it each time? I tried removing that part and then I got lost and put it back.

 

I feel like I am getting close, but I don't know where to go from here.

	int answer;

	public int check(int steps, int step){
		
		if(step<steps){
			answer++;
			check(steps,step+1);
			check(steps,step+3);
			check(steps,step+5);
		}

		return answer;
	}

[Andre S. Veteran]

In your example you're doing nothing with your return value; instead you're using an outer variable to hold the result. Your function could return void and do the same thing. Use the return value!

 

Example of computing a sum recursively: 

 

public int Sum(int[] elems, int index) {
    if (index >= elems.Length) {
        return 0;
    }
    else {
        return elems[index] + Sum(elems, index + 1);
    }
}
Console.WriteLine(Sum(elems, 0)); // prints the sum of all elements in elems starting at 0

Example of counting the number of even elements recursively:

 

public int NumberOfEvenElements(int[] elems, int index) {
    if (index >= elems.Length) {
        return 0;
    }
    if (elems[index] % 2 == 0) {
        return 1 + NumberOfEvenElements(elems, index + 1);
    }
    else {
        return NumberOfEvenElements(elems, index + 1);
    }
}

Console.WriteLine(NumberOfEvenElements(elems, 0)); // prints the number of even elements in elems

In both cases at each step along the way we return either a constant value if we're at the boundary condition, or the result of calling ourselves recursively if we're not. So it's a similar idea in your case. Your function should just be an if/else statement that returns something different depending on whether the boundary condition is met.

[Andre S. Veteran]

If you have any experience with tree traversal using recursive functions then your problem is really just an application of that. It could be fruitful to draw your problem on paper as a graph where each link is marked by the number of steps (1, 3 or 5) you took to get there and each node holds the total number of steps climbed so far. Then figure out a strategy to traverse this tree so that what you end up with is the number of nodes that are equal or greater to the number of steps in the staircase. If that's too difficult you could start with a even simpler problem like summing the values of all nodes or counting the number of nodes that fit some condition (like being even or non zero or whatever).

[MacemanD]

I believe I got it working. But, I'm still using the 'answer' variable, and I'm not using the return value in the recursion - trying this was making it more difficult for me.

	int answer;

	public int check(int steps, int step){
		
		if (step >= steps) {
			answer++;
		}
		else {
			int num = check(steps,step+1) + check(steps,step+3) + check(steps,step+5);
		}
		
		return answer;
	}

I think it is working like this. It is due today, and I already turned it in, so just for curiosity's sake, what would your code look like?

[francescob]

What? No "to understand recursion you must first understand recursion" jokes yet? :(

 

Assume at the top of the stairs there is a flat surface so it doesn't matter if the user oversteps on their last step.

 

Phew, that part almost got me trippin' ! :O

[Andre S. Veteran]

Ah, that's the basic idea. It's a bit confused because you return int and perform the summing but you don't do anything with it, instead you use this outer variable to keep the result. In effect you could change the return type for void. It's not a "clean" recursive implementation but it works I guess. Here's how I would do it:

 

int WaysToClimbStaircase(int totalSteps, int lastStep) {
    if (lastStep >= totalSteps) {
        return 1;
    }
    return 
        WaysToClimbStaircase(totalSteps, lastStep + 1) +
        WaysToClimbStaircase(totalSteps, lastStep + 3) +
        WaysToClimbStaircase(totalSteps, lastStep + 5);
}
	
void Main()
{
    Console.WriteLine(WaysToClimbStaircase(2, 0));
}

If you want to avoid having to pass the extraneous 0 you can create a wrapper function that takes just the number of steps and calls the implementation with the 0.

Just because I like to promote F# here's how it would look like in F#:

 

let check n =
    let rec loop s =
        if s >= n then 1
        else (loop (s + 1)) + (loop (s + 3)) + (loop (s + 5))
    loop 0

printfn "%d" (check 3)