Python - Ways to Reach the n’th Stair

Problem Statement

Given n stairs, you can climb 1 step or 2 steps at a time. Find the number of distinct ways to reach the n-th stair.

Example

Input: n = 3  

Output: 3  

Explanation: (1,1,1), (1,2), (2,1)

Input: n = 5  

Output: 8  

Explanation: Possible ways - (1,1,1,1,1), (1,1,1,2), (1,1,2,1), (1,2,1,1), (2,1,1,1), (1,2,2), (2,1,2), (2,2,1)

Approach 1: Recursion (Exponential Time Complexity)

At each step, we either:

Take one step (reducing n by 1).

Take two steps (reducing n by 2).

The recurrence relation is:

f(n)=f(n−1)+f(n−2)

This is similar to the Fibonacci sequence.

def count_ways(n):

    if n == 0 or n == 1:

        return 1

    return count_ways(n-1) + count_ways(n-2)

# Example

print(count_ways(3))  # Output: 3

print(count_ways(5))  # Output: 8