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 nth, 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 nth step.
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.
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.
You may have recognised that our countWays() function is based on a very similar recursive formula used to calculate the nth term of the Fibonacci sequence.