-1

Problem Statement

Suppose there is a staircase that you can climb in either 1 step, 2 steps, or 3 steps. In how many possible ways can you climb the staircase if the staircase has n steps? Write a recursive function to solve the problem.

Example:

n == 1 then answer = 1

n == 3 then answer = 4 ,
The output is 4 because there are four ways we can climb the staircase:

1 step + 1 step + 1 step
1 step + 2 steps
2 steps + 1 step
3 steps
n == 5 then answer = 13

Solution

def staircase(n):
    if n <= 0:
        return 1

    if n == 1:
        return 1
    elif n == 2:
        return 2
    elif n == 3:
        return 4

    return staircase(n - 1) + staircase(n - 2) + staircase(n - 3)

I understand the basics of how recursion works.

I think of recursion as an approach to solve a problem by solving its smaller parts first and then combining the result to get the final answer. We set a base condition for the smallest part and start building our solution from there.

In that sense, I understand the famous recursion problems of factorial, palindrome, Fibonacci, and tower of Hanoi where it is very clear that the smaller parts make up the larger part and recursion takes care of the problem elegantly.

But with the staircase problem, I am simply not able to wrap my head around how the author came up with this solution and why it is working?

I am seeking help more with understanding and the thought process behind this solution rather than the program itself as I have already looked at the stack trace and have a fair idea about the execution of it.

EDIT - Recursion on staircase

for those who are interested, the linked post has a more in-depth explanation to the same problem

Ganesh Thampi
  • 111
  • 1
  • 2
  • 9
  • 5
    To climb n>3 stairs, you either [a] first climb 1 stair and then climb n-1 stairs, [b] first climb 2 stairs and then climb n-2 stairs, or [c] first climb 3 stairs and then climb n-3 stairs. Counting the ways, it's S(n) = S(n-1) + S(n-2) + S(n-3) – Paul Hankin Jun 05 '20 at 06:23

1 Answers1

1

To climb n>3 stairs, you either [a] first climb 1 stair and then climb n-1 stairs, [b] first climb 2 stairs and then climb n-2 stairs, or [c] first climb 3 stairs and then climb n-3 stairs. Counting the ways, it's S(n) = S(n-1) + S(n-2) + S(n-3)

Paul Hankin
  • 54,811
  • 11
  • 92
  • 118