Algorithm Problem: Recursion (Climbing Staircase)

Me and a group of friends like to solve algorithmic problems / puzzles during our free time. I’d like to share a fun recursion problem that we worked on yesterday.

A problem like this is expected in an interview since it’s small enough to be able to code up quickly if you know the trick.

Tim has a staircase with height n and he likes to climb each staircase 1, 2, or 3 steps at a time. Find out how many ways there are to reach the top of the staircase. Given the respective height, find and print the number of ways he can climb the staircase.

For example:

There’s only one way to climb a staircase with height of 1.

There are two ways of climbing a staircase with hight of 2. You can take two hops or one 2 hops.

There are four ways of climbing a staircase with height of 3. You can do three 1 hops, one 3 hops, or one 2 hops + one 1 hops. Notice the last one gives your 2 combination so the total number of ways is 4.