# ---
# jupyter:
#   jupytext:
#     text_representation:
#       extension: .py
#       format_name: light
#       format_version: '1.5'
#       jupytext_version: 1.15.2
#   kernelspec:
#     display_name: Python 3
#     language: python
#     name: python3
# ---

# + [markdown] graffitiCellId="id_v5swjqy"
# ### 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`<br>
#    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`
#

# + [markdown] graffitiCellId="id_74s7rzj"
# ### Exercise - Write a recursive function to solve this problem

# + graffitiCellId="id_yv3ymjf"
"""
param: n - number of steps in the staircase
Return number of possible ways in which you can climb the staircase
"""
def staircase(n):
    '''Hint'''
    # Base Case - What holds true for minimum steps possible i.e., n == 0, 1, 2 or 3? Return the number of ways the child can climb n steps.
    
    # Recursive Step - Split the solution into base case if n > 3.
    
    pass

# +
# Solution
## Read input as specified in the question.
## Print output as specified in the question.


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)


# + [markdown] graffitiCellId="id_w7lklez"
# <span class="graffiti-highlight graffiti-id_w7lklez-id_brqvnra"><i></i><button>Show Solution</button></span>

# + graffitiCellId="id_qnr80ry"
def test_function(test_case):
    n = test_case[0]
    solution = test_case[1]
    output = staircase(n)
    if output == solution:
        print("Pass")
    else:
        print("Fail")


# + graffitiCellId="id_6g7yxbj"
n = 3
solution = 4
test_case = [n, solution]
test_function(test_case)

# + graffitiCellId="id_1q0pz7y"
n = 4
solution = 7
test_case = [n, solution]
test_function(test_case)

# + graffitiCellId="id_p3uxb7h"
n = 7
solution = 44
test_case = [n, solution]
test_function(test_case)
