Interview Questions

Step-by-step solution for step counting using recursion
A lecturer at Hack Reactor made this comment on Quora in response to a question about preparing for the Hack Reactor admission's challenge:
One big thing that will help you: get intimately familiar with the concepts of recursion and JavaScript closures ... they will come up early in your interactions with Hack Reactor (and are just great things to understand in general).
Below we'll cover a clever question that we'll solve using recursion. In a previous post we covered some questions regarding closures.

## Question

Suppose you want climb a staircase of N steps, and on each step you can take either 1 or 2 steps. How many distinct ways are there to climb the staircase? For example, if you wanted to climb 4 steps, you can take the following distinct number of steps:
1) 1, 1, 1, 1 2) 1, 1, 2 3) 1, 2, 1 4) 2, 1, 1 5) 2, 2
So there are 5 distinct ways to climb 4 steps. We want to write a function, using recursion, that will produce the answer for any number of steps.

## Solution

We'll try to build up a list of solutions for N starting from the smallest staircase. If we want to climb a staircase of 1 step (N = 1), then we can only take 1 step to reach the top. Therefore, the solution when N = 1 is 1. If we want to climb a staircase of 2 steps (N = 2), we can take either 2 steps, or 1 step and 1 step to reach the top. So for N = 2, the solution is 2. N = 1 Solution = 1 N = 2 Solution = 2 Now what about 3 steps? N = 3 Solution = 3 N = 4 Solution = 5 (from example above) We can see a pattern beginning to emerge. The solution for N steps is equal to the solutions for N - 1 steps plus N - 2 steps. Let's confirm this. N = 3 Solution = (N - 1 steps) + (N - 2 steps) Solution = (N = 2) + (N = 1) Solution = (2) + (1) Solution = 3 N = 4 Solution = (N - 1 steps) + (N - 2 steps) Solution = (N = 3) + (N = 2) Solution = (3) + (2) Solution = 5 It checks out so far! The solution to this problem requires recursion, which means to solve for a particular N, we need the solutions for previous N's. Our code solution below will attempt to mimic this process of recursion to solve for any N.

## Code

```function countSteps(N) {

// just as in our solution explanation above, we know that to climb 1 step
// there is only 1 solution, and for 2 steps there are 2 solutions
if (N === 1) { return 1; }
if (N === 2) { return 2; }

// for all N > 2, we add the previous (N - 1) + (N - 2) steps to get
return countSteps(N - 1) + countSteps(N - 2);

}

// the solution for N = 6 will recursively be solved by calculating
// the solution for N = 5, N = 4, N = 3, and N = 2 which we know is 2
countSteps(6);
```
```def countSteps(N):

# just as in our solution explanation above, we know that to climb 1 step
# there is only 1 solution, and for 2 steps there are 2 solutions
if N == 1:
return 1

if N == 2:
return 2

# for all N > 2, we add the previous (N - 1) + (N - 2) steps to get
return countSteps(N - 1) + countSteps(N - 2)

# the solution for N = 6 will recursively be solved by calculating
# the solution for N = 5, N = 4, N = 3, and N = 2 which we know is 2.
print countSteps(6)
```
mrdaniel published this on 12/6/15 |
• +
• 3
• -
• Hope you like another way to solve it (Python): ``` def steps(N): lst=[0,1,2] for i in range (3,N+1): sum=lst[i-1]+lst[i-2] lst.append(sum) return lst[N] ```
• +
• 3
• -
• I can see that the above code does work, but I'm disappointed that we don't get a deeper explanation for WHY it works. As presented, I don't think it helps give the reader a better understanding of how to use recursion. Here was my solution, which was rather different (but still works!). The basic premise is imagining that we are selecting two of the steps at a time, and then adding all the possible combinations for the remaining steps: ```function recursiveSteps(steps) { var total = 1; for (var i = 2; i <= steps; i++) { total += recursiveSteps(steps - i); } return total; }```
• +
• 2
• -
• So when I was thinking about the problem, looking at 3 and 4 steps.. I was also able to arrive at Num_of_Ways = (n-1) + (n-2) This doesn't work when you arrive at 5 steps as it this equation would give 7 ways instead of 8. So how do you know to put the equation into recursion vs just having the above equation? Thank you!
• +
• 1
• -
• Wanted to post my solution as well. Adapted from the recursion example found in Eloquent JavaScript, Chapter 3: eloquentjavascript.net/ ```function stairCounter(stairs){ var count = 0; var start = 0; function find(start){ if(start === stairs){ count += 1 } else if(start > stairs) return null else{ return find(start + 2) || find(start + 1) } } find(start); return count; }```
• +
• 1
• -
• ``` def countSteps(N): if N < 3: return N return countSteps(N - 1) + countSteps(N - 2) ```
• +
• 0
• -
• While recursion is the most _obvious_ solution here (as others have noted, it reduces to Fibonacci), it is the _wrong_ solution--so much duplicated computation. fib(6) = fib(4) + fib(5) fib(6) = fib(4) + (fib(3) + fib(4)) fib(6) = (fib(2) + fib(3)) + (fib(3) + (fib(2) + fib(3))) fib(6) = (fib(2) + (fib(1) + fib(2))) + ((fib(1) + fib(2)) + (fib(2) + (fib(1) + fib(2))) fib(6) = 2 + 1 + 2 + 1 + 2 + 2 + 1 + 2 fib(6) = 13 TommyWommy's dynamic programming solution is much better.
• +
• -1
• -
• Fibonacci ``` function fibonacci(num) { if (num <= 1) return 1; return fibonacci(num - 1) + fibonacci(num - 2); } ```