Teaser: You can easily do this calculation in less than a millisecond. Details follow ...
Which one is "better"?
The question of which algorithm is “better” may relate to runtime, as well as to other things, such as an implementation style.
The implementation of Staircase shorter, more concise, and IMHO more readable. And more importantly: it does not include the state . The c2 variable you introduced there destroys the benefits (and beauty) of a purely functional recursive implementation. This can be easily fixed, although the implementation is then more similar to Staircase .
Measurement performance
Regarding the issue of runtime: properly measuring runtime in Java is complicated.
Related reading:
There are several options for correct and reliable runtime measurement. Besides a profiler like VisualVM , there are frameworks like JMH or Caliper , but admittedly using them can be a bit of an effort.
For the simplest form of a very simple manual Java Microbenchmark, you should consider the following:
- Run the algorithms several times to give JIT the ability to hit
- Run algorithms one at a time, and not just one after another
- Running algorithms with increasing input size
- Somehow save and print the calculation results to prevent optimization of the calculations.
- Do not print anything on the console during the test.
- Consider Timings May Be Distorted By The Garbage Collector (GC)
Again: These are just rules of thumb , and there may still be unexpected results (see the links above for more details). But with this strategy, you usually get a good idea of performance, and at least you can see if there are significant differences between the algorithms.
Differences between approaches
The Staircase implementation and the Steps implementation are not very different.
The main conceptual difference is that the Staircase implementation counts down , and the Steps implementation counts up .
The main difference that actually affects performance is how the base case is handled (see Recursion on Wikipedia). In your implementation, you avoid invoking the method recursively when it is not necessary, at the expense of some additional if . The Staircase implementation uses very general base case handling, simply checking to see if n < 0 .
You can consider the "intermediate" solution, which combines the ideas of both approaches:
class Staircase2 { public static int counting(int n) { int result = 0; if (n >= 1) { result += counting(n-1); if (n >= 2) { result += counting(n-2); if (n >= 3) { result += counting(n-3); } } } else { result += 1; } return result; } }
It is still stateless recursively and summarizes intermediate results, avoiding many “useless” calls using multiple if queries. It is already noticeably faster than the original Staircase implementation, but still slower than the Steps implementation.
Why are both solutions slow
In both implementations, there is nothing that could be calculated. The method consists of several if and some additions. The most expensive thing here is, actually, recursion, with a really nested call tree.
And here's the key point: this is a tree call. Imagine what it calculates in a certain number of steps, as a "hierarchy of pseudo-code calls":
compute(5) compute(4) compute(3) compute(2) compute(1) compute(0) compute(0) compute(1) compute(0) compute(0) compute(2) compute(1) compute(0) compute(0) compute(1) compute(0) compute(3) compute(2) compute(1) compute(0) compute(0) compute(1) compute(0) compute(0) compute(2) compute(1) compute(0) compute(0)
One can imagine that it grows exponentially when the number gets larger. And all the results are calculated hundreds, thousands or or millions of times. This can be avoided
Fast decision
The main idea of speeding up computing is to use Dynamic Programming . This basically means that the intermediate results are saved for later retrieval, so they do not need to be calculated again and again.
It is implemented in this example, which also compares the execution time of all approaches:
import java.util.Arrays; public class StaircaseSteps { public static void main(String[] args) { for (int i = 5; i < 33; i++) { runStaircase(i); runSteps(i); runDynamic(i); } } private static void runStaircase(int max) { long before = System.nanoTime(); long sum = 0; for (int i = 0; i < max; i++) { sum += Staircase.counting(i); } long after = System.nanoTime(); System.out.println("Staircase up to "+max+" gives "+sum+" time "+(after-before)/1e6); } private static void runSteps(int max) { long before = System.nanoTime(); long sum = 0; for (int i = 0; i < max; i++) { sum += Steps.step(i); } long after = System.nanoTime(); System.out.println("Steps up to "+max+" gives "+sum+" time "+(after-before)/1e6); } private static void runDynamic(int max) { long before = System.nanoTime(); long sum = 0; for (int i = 0; i < max; i++) { sum += StaircaseDynamicProgramming.counting(i); } long after = System.nanoTime(); System.out.println("Dynamic up to "+max+" gives "+sum+" time "+(after-before)/1e6); } } class Staircase { public static int counting(int n) { if (n < 0) return 0; else if (n == 0) return 1; else return counting(n - 1) + counting(n - 2) + counting(n - 3); } } class Steps { static int c2 = 0; static int stairs; public static int step(int c) { c2 = 0; stairs = c; return step2(0); } private static int step2(int c) { if (c + 1 < stairs) { if (c + 2 <= stairs) { if (c + 3 <= stairs) { step2(c + 3); } step2(c + 2); } step2(c + 1); } else { c2++; } return c2; } } class StaircaseDynamicProgramming { public static int counting(int n) { int results[] = new int[n+1]; Arrays.fill(results, -1); return counting(n, results); } private static int counting(int n, int results[]) { int result = results[n]; if (result == -1) { result = 0; if (n >= 1) { result += counting(n-1, results); if (n >= 2) { result += counting(n-2, results); if (n >= 3) { result += counting(n-3, results); } } } else { result += 1; } } results[n] = result; return result; } }
The results on my PC are as follows:
... Staircase up to 29 gives 34850335 time 310.672814 Steps up to 29 gives 34850335 time 112.237711 Dynamic up to 29 gives 34850335 time 0.089785 Staircase up to 30 gives 64099760 time 578.072582 Steps up to 30 gives 64099760 time 204.264142 Dynamic up to 30 gives 64099760 time 0.091524 Staircase up to 31 gives 117897840 time 1050.152703 Steps up to 31 gives 117897840 time 381.293274 Dynamic up to 31 gives 117897840 time 0.084565 Staircase up to 32 gives 216847936 time 1929.43348 Steps up to 32 gives 216847936 time 699.066728 Dynamic up to 32 gives 216847936 time 0.089089
Small changes in order of order or so (“microoptimization”) may have little effect or make a noticeable difference. But using a completely different approach can make a real difference.