Count ways to reach the nth stair with

There are n stairs, we need to find number of ways a person can reach nth stair from bottom; if he can climb either 1 or 2 or 3 stairs at a time.

Example 1: No of ways to reach 4th stair

Input: 4
Output: 7

Example 2: No of ways to reach 7th stair

Input: 7
Output: 44

Solutions

Method 1: Recursion

As per the question the person can reach nth stair either taking 1 or 2 or 3 steps at a time, that means the person can reach nth stair either from (n-1)th stair or (n-2)nd stair or (n-3)rd stair. Now if we find number of ways a person can reach to n-1, n-2 and n-3 stair and add them, we should get the answer.

We also know that, the person is standing at 0th stair and reaching there is only possible in one way (just jumping), additionally there is no way to reach < 0 th stair; we can use these two as base condition.

package com.cb.recursion;

/*
 * Possible steps 1 or 2 or 3 at a time
 * */
public class R10_ReachNthStair {
    public static int noOfWays(int n) {
        if (n < 0)
            return 0;
        if (n == 0)
            return 1;

        return noOfWays(n - 1) + noOfWays(n - 2) + noOfWays(n - 3);
    }

    public static void main(String[] args) {
        System.out.println(noOfWays(4));
        System.out.println(noOfWays(7));
    }
}