A function to calculate the number of different paths up a flight of stairs that has n-steps, if you can only move 1,2,3 steps at a time.

Stairway-Problem-Recursive-Solution.py

def num_paths(n):
    """
    A function to calculate the number of different paths up a flight of stairs that has n-steps, if you can only move
        1,2,3 steps at a time.
    """

    # Base cases:
    if n < 0:
        return 0
    if n == 1:
        return 1
    elif n == 2:
        return 2
    elif n == 3:
        return 4

    # Inductive Step:
    return num_paths(n - 1) + num_paths(n - 2) + num_paths(n - 3)


print(num_paths(100))

This problem can be viewed as a Fibonacci sequence, as implementing a function to solve Fibonacci is also very similar.

We can make this type of algorithm faster by implementing memoization for the use of the recursive calls. Doing so would turn out algorithm from the time complexity of O(3^n) to O(N), a major win in terms of efficiency. I'll get around to posting a revised version of the algorithm to this gist as soon as I have the chance too.

Keep in mind that this is a top-down implementation of this algorithm, there is a way to do a bottom-down version via traditional loops, but I wanted to practice recursion, and this problem is much more eloquent and easier to understand using recursion.