The Climbing Stairs Puzzle

Imagine a staircase with n steps. As you are climbing up this staircase, you either climb one or two steps at a time. The aim of this computing puzzle is to find out, using an algorithm, in how many distinct ways can you climb to the top?

Confused by this puzzle? Let’s look at an example where you are climbing a small staircase of only 4 steps. Remember, for every “step” you make, you can either climb 1 or two steps at a time. Which means there are 5 different ways you can climb this staircase as shown on the pictures below:

A Recursive Approach?

Let’s investigate this problem, “step by step”!!

We can assume that n, the total number of steps in the staircase is a positive integer.
The output of our algorithm is the total number of distinct ways we can climb this stair.

So we can easily deduct that:

• If n=0, the output should be zero too.
• If n=1, the output will be 1 (there is only way to climb this step).
  
• If n=2, the output will be 2 (there are only two ways to climb this step).
  
• For any n number of steps greater than 2, we notice that to reach the n^th, we have to first reach either step (n-1) or step (n-2).
  
  So to count the number of ways we can reach step n, we can use the following recursive formula:
  if n>2 then countWays(n) = countWays(n-1) + countWays(n-2)
  countWays(2) = 2
  countWays(1) = 1
  where countWays(n) is a function that returns the number of ways you can reach the n^th step.

Python Code

To implement an algorithm based on this formula we will use a recursive function called countWays() that takes one parameter, n, the position of the step we aim to reach. The function will return the number of possible distinct ways to reach this step when climbing up from the bottom of the stairs.

Tracing a Recursive Algorithm

You can visualise/trace this recursive algorithm using recursivevisualization.com.

Your Task

What about if as you are climbing up this staircase, you could climb 1, 2 or 3 steps at a time?

Adapt the above python code to implement this small change in the climbing stairs puzzle.

Fibonacci Numbers

You may have recognised that our countWays() function is based on a very similar recursive formula used to calculate the n^th term of the Fibonacci sequence.

Solution...

The solution for this challenge is available to full members!
Find out how to become a member:
➤ Members' Area