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:
## 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...

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.
You need to be a premium member to see the rest of this question and code.

With our large collection of challengs, tutorials, and solutions, we make it easy for you to become a better coder, prepare for interviews, and learn new skills from more experienced coders.

- 200+ Coding Challenges
- Mock Interview Questions
- 500,000+ Code Solutions
- Algorithm Tutorials
- Interview Prep Courses

mrdaniel
published this on 12/6/15 **|**

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; }

iccir919

commented on 06/10/16

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!

michaelolor

commented on 06/01/16

1

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]

TommyWommy

commented on 05/12/16

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; }

paabrown

commented on 06/22/17

Login to submit a comment