HackerRank challenge to count ways to climb a staircase, solved using Java Fork Join
The reason your code still runs slow is the huge increase in how often you calculate the smaller steps.

If you want to find the number of ways for N steps. You calculate (N-1) once, (N-2) 2 times, (N-3) 4 times ..., (N-10) 274 times, ... (N-24) over a million times

Fun fact: the number of times you calculate (N-x) = calculateNumberOfWays(x).

oopexpert solved this by storing all the previous steps in a cache, so you calculate each step exactly once. This means it now takes O(N) recursive calls the first time the algorithm is called. And only 1 call afterwards (since it now became a lookup instead of a calculation).

The downside is that you actually store all intermediate results. An alternative solution is to not use recursion at all but work your way from the bottom up and store only the last 3 steps. An implementation could look like this:

public static int calculateNumberOfWays(int stairHeight){
    if(stairHeight &lt; 0){
        return 0;
    }
    if(stairHeight &lt; 2){
        return 1;
    }
    int twoStepsBack = 0;
    int previousStep = 1;
    int currentStep = 1;
    for(int i = 2; i &lt;= stairHeight; i++){
        int nextStep = twoStepsBack + previousStep + currentStep;
        twoStepsBack = previousStep;
        previousStep = currentStep;
        currentStep = nextStep;
    }
    return currentStep;
}


This also has the next big advantage of not using recursion at all. Recursion in java is only good if you have a limited number of recursive steps. Otherwise you'll quickly run into a StackOverFlowError.

For example, running the following tiny program:

public static void main(String[] args) {
    recursionTest(0);
}

public static void recursionTest(int step){
    System.out.println(step);
    recursionTest(step+1);
}


Threw an error after printing 11412. For your problem giving input of over 10000 would be insane so it's probably not really an issue though which brings me to the next problem with your solution.

Both our solutions can only solve up to stairHeight 36. At 37 we get an integer overflow. Changing it from int to long allows up to 72.

If you want to work with really BIG integers, java has a BigInteger class. I'll leave the conversion to BigInteger to you (it's not that hard, as long as you remember to use someBigNumber.add(otherBigNumber) instead of the normal +).

Just for fun I tried to run it with n=10000 but the result is huuuuge (as expected). To give an idea, if I take result.toString().lenth() it's still 2647. But at least the program calculates this almost instantly :)