Climb Stairs

int countDistinctWayToClimbStair(long long nStairs)
{
    // Base case 1: If there are fewer than 0 stairs, no way to climb.
    if(nStairs < 0)
        return 0;

    // Base case 2: If there are exactly 0 stairs, there is 1 way (by staying at the ground).
    if(nStairs == 0)
        return 1;

    // Recursive call: The number of ways to reach the top is the sum of:
    // 1. The number of ways to reach n-1 stairs, then taking 1 step.
    // 2. The number of ways to reach n-2 stairs, then taking 2 steps.
    int ans = countDistinctWayToClimbStair(nStairs-1)
        + countDistinctWayToClimbStair(nStairs-2);

    return ans;
}

Example Walkthrough (for nStairs = 4):

• Call 1: countDistinctWayToClimbStair(4)
  • Calls countDistinctWayToClimbStair(3) + countDistinctWayToClimbStair(2)
• Call 2: countDistinctWayToClimbStair(3)
  • Calls countDistinctWayToClimbStair(2) + countDistinctWayToClimbStair(1)
• Call 3: countDistinctWayToClimbStair(2)
  • Calls countDistinctWayToClimbStair(1) + countDistinctWayToClimbStair(0)
• Call 4: countDistinctWayToClimbStair(1)
  • Calls countDistinctWayToClimbStair(0) + countDistinctWayToClimbStair(-1)
• Base Cases:
  • countDistinctWayToClimbStair(0)returns 1 (you reached the top).
  • countDistinctWayToClimbStair(-1) returns 0 (invalid, no way to climb).

Now, the function starts returning values back up through the recursive calls:

• countDistinctWayToClimbStair(1) returns 1 + 0 = 1
• countDistinctWayToClimbStair(2) returns 1 + 1 = 2
• countDistinctWayToClimbStair(3) returns 2 + 1 = 3
• countDistinctWayToClimbStair(4) returns 3 + 2 = 5

So, for nStairs = 4, the total number of distinct ways to climb the stairs is 5.