Interview Questions

  • View all tutorials
  • blank
  • 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.

    Sources

    https://www.quora.com/How-did-you-prepare-for-Hack-Reactors-admissions-challenge https://www.glassdoor.com/Interview/You-are-climbing-a-stair-case-Each-time-you-can-either-make-1-step-or-2-steps-The-staircase...

    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
      // an answer recursively
      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
      # an answer recursively
      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)
    
    Run Code
    Run Code
    mrdaniel published this on 12/6/15 | javascript, bootcamp, recursion, Fullstack Academy, Hack Reactor, Google
    Comments
  • +
  • 2
  • -
  • 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]
    
  • +
  • 1
  • -
  • Wanted to post my solution as well. Adapted from the recursion example found in Eloquent JavaScript, Chapter 3: http://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
  • -
  • 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!
  • +
  • 0
  • -
  • 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;
    }
    Log in to submit a comment.