I'm trying to solve the problem of "count ways to reach the nth step in a staircase" with recursion. When given a number of stairs to climb, I have to calculate the number of ways to climb taking either 1 or 2 steps at a time. For example, if there are 4 stairs, we would return 5 since we would have:
* 1 1 1 1
* 1 1 2
* 1 2 1
* 2 1 1
* 2 2
My code is currently throwing a stack overflow exception:
public static int countWaysToClimb(int stairs) {
return countWaysToClimbHelper(stairs, 0, 0);
}
public static int countWaysToClimbHelper(int sumNeeded, int currentSum, int possibleCombos) {
// base - we will reach this base multiple times
if (sumNeeded == currentSum) {
possibleCombos++;
// if we already found a combo, we need to reset the sum
countWaysToClimbHelper(sumNeeded,0,possibleCombos);
}
else if (currentSum > sumNeeded) {
return 0;
}
// recurse - add 1 and then add 2
countWaysToClimbHelper(sumNeeded,currentSum+1,possibleCombos);
countWaysToClimbHelper(sumNeeded,currentSum+2,possibleCombos);
return possibleCombos;
}
Thank you!
There are some issues in your code:
if (sumNeeded == currentSum)
is meat instead of returning the number of combinations. You created an infinite recursion that inevitably leads to a StackOverflowError
. You have to place a return statement inside the curly braces after the first if
in your code. And comment out the first recursive call (with 0
sum passed as an argument) you'll face the second problem: for any input, your code will yield 0
.countWaysToClimbHelper()
are omitted. Variable possibleCombos
isn't affected by these calls. Each method call allocates its own copy of this variable possibleCombos
on the stack (a memory aria where JVM stores data for each method call), and their values are not related anyhow.Before moving further, let me recap the basics of recursion.
Every recursive method should contain two parts:
sumNeeded == currentSum
- the return value is 1
, i.e. one combination was found;sumNeeded > currentSum
- the return value is 0
.So the fixed code might look like that:
public static int countWaysToClimb(int stairs) {
return countWaysToClimbHelper(stairs, 0);
}
public static int countWaysToClimbHelper(int sumNeeded, int currentSum) {
// base - we will reach this base multiple times
if (sumNeeded == currentSum) {
return 1;
} else if (currentSum > sumNeeded) {
return 0;
}
// recurse - add 1 and then add 2
int possibleCombos = 0;
possibleCombos += countWaysToClimbHelper(sumNeeded,currentSum + 1);
possibleCombos += countWaysToClimbHelper(sumNeeded,currentSum + 2);
return possibleCombos;
}
Note:
countWaysToClimb()
without using a helper-method. For that, instead of tracking the currentSum
you need to subtract the number of steps from the sumNeeded
when the method is called recursively.