Problem : How to speed up a recursion method using other techniques.
Simple Fibonacci sequence method uses recursion to output the Nth number of the input.
Any suggestions would be great, thank you.
ex; putting in 50 would take nearly a minute to finally get an output.
Edit: Change of problem text, as it wasn't recursion being too slow, it was my code.
public static long cycle(int x) {
if(x<=1) {
return x;
} else {
return cycle(x-1)+cycle(x-2);
}
}
Let's think about the fundamental problem here. You want your code to perform faster on the same hardware, an important software process called optimization.
During optimization, you'll need to profile your application to determine what is the slowest component and improve upon that. In your case, I can guess with a good degree of certainty in that the slowest component of your program here is the function call. Plotting the nth Fibonacci term against the number of function calls we get:
as you can see, the growth is exponential. Note: there are mathematical ways to figure this out, notably as explained on this page. Exponential growth in time complexity is always something to avoid if your intentions are to make a fast executing function (granted, there are functions that have to be exponential but this is not one of them). Looking at cycle(50), taking over 4 * 10^10 function calls, you said it finished in nearly a minute which equates to about 666.6 million function calls per second (or 1 call per 1.5 ns), hardly seems fair to call java slow based on that. The bottom line is, it doesn't matter how good or fast the compiler's optimization techniques get, it won't be able to fix your time complexity, it can only make each operation slightly faster (read tail-call optimization if you want to know more).
The primary issue you are having here is that you are recomputing the same Fibonacci numbers many many times, think of how many times you are recomputing cycle(2). That's where the exponential complexity is coming from, recomputing the same Fibonacci numbers many many times, which is useless.
The easiest way to solve the issue is via iteration but you've expressed your disinterest in iterator.
The next easy way is to use a look up table (LUT) storing precomputed Fibonacci numbers in an array for fast access. The problem with this approach can be easily shown below:
The graph above shows the effects of the LUT of n up to 10. whilst we have reduced the power of the exponent, we are still dealing with exponentials which doesn't solve the problem entirely (suppose you need to do cycle(100) what then?).
The solution is to use memorization as mentioned in user 1.618's comment. What this means is to save the result of each Fibonacci term as you are calculating it, generating the LUT as you go, never recomputing any result twice.
The following graph demonstrates the effects of this:
at cycle(50), you'll need 97 method calls, which at a speed of 1.5 ns/call will finish in 145.5 ns, faster than you can blink (it probably won't do it that fast due to additional time looking at the LUT as well as well as not warming up as much).
Implementing this in java, we get:
private static long[] fib_numbers;
public static long cycle(int x){
if(fib_numbers == null || fib_numbers.length <= x){
fib_numbers = new long[x + 1];
}
return cycle_rec(x);
}
private static long cycle_rec(int x) {
if(x <= 1){
return x;
}else if(fib_numbers[x] != 0){
// previously computed result exists, return directly
return fib_numbers[x];
}else{
// compute and store cycle(x)
fib_numbers[x] = cycle_rec(x-1)+cycle_rec(x-2);
return fib_numbers[x];
}
}
the array fib_numbers holds the LUT we dynamically generate per method call. We expose a public method cycle() to setup the array for use before internally calling cycle_rec() (our recursive function).
The problem is the algorithm, not "Java's recursion". Although Fibonacci numbers, mathematically, are usually defined recursively:
F(0) = 0
F(1) = 1
F(n) = F(n - 2) + F(n - 1) if n >= 2
or something equivalent, that is the wrong way to implement it when writing a computer program to compute it. Using a loop lets you compute F(n) in O(n) time; using recursion will make the computation O(F(n)), which is exponential rather than linear. The problem is that your are computing many of the F(n)'s repeatedly. If you compute F(8) by computing F(7) + F(6), you will compute F(7) by adding F(6) + F(5), and so on down; then you go back up to the top and compute F(6), which you've already computed, but this algorithm will require you to compute it again, as well as everything else smaller. That is why the program is too slow. And a recursive program would be slower no matter what language you write it in, including assembly.
To increase the speed you need to write better code :).
First check whether your code can be improved further? If not then think about the bottle necks you are facing. Suppose it is taking hell lot of time to compute for values more than 1000. Then in that case you can think of storing all the intermediate values in an array and in that case for any value from 0 to 999 the answer will be available in O(1) time.
Other areas may be related to tuning of JVM of which I am not much aware of :)
The problem you have is that the number of method calls is equal to the solution as everything needs to be decomposed to 1+1+1+ etc. This is O(e^n) which is very bad for performance.
A faster solution is to use iteration. This is much fast than recursion even with memorization the first time. If you want memorization, you may as well generate all possible values you can store in a long on start up (takes about 3 ms) and after that do an array lookup (takes about 5 ns)
static final long[] fibonacci = new long[92];
static {
fibonacci[1] = fibonacci[2] = 1;
for(int i = 3; i < fibonacci.length; i++)
fibonacci[i] = fibonacci[i-1] + fibonacci[i-2];
}
// takes about 5 ns.
public static long cycle(int x) { return fibonacci[i]; }
Another solution is to calculate the fibonacci numbers. This is only an estimate with double but has almost O(1) time.
static final double sqrt5 = Math.sqrt(5);
static final double c1 = (1 + sqrt5) / 2;
static final double c2 = (1 - sqrt5) / 2;
static double estimateFibonacci(int n) {
double v = (Math.pow(c1, n) - Math.pow(c2, n)) / sqrt5;
return v < Long.MAX_VALUE ? Math.round(v) : v;
}
public static void main(String... args) {
for (int i = 0; i < 100; i++)
System.out.println(i + ": " + estimateFibonacci(i));
}
prints
0: 0.0
1: 1.0
2: 1.0
3: 2.0
4: 3.0
5: 5.0
6: 8.0
7: 13.0
8: 21.0
9: 34.0
10: 55.0
11: 89.0
12: 144.0
13: 233.0
14: 377.0
15: 610.0
16: 987.0
17: 1597.0
18: 2584.0
19: 4181.0
20: 6765.0
21: 10946.0
22: 17711.0
23: 28657.0
24: 46368.0
25: 75025.0
26: 121393.0
27: 196418.0
28: 317811.0
29: 514229.0
30: 832040.0
31: 1346269.0
32: 2178309.0
33: 3524578.0
34: 5702887.0
35: 9227465.0
36: 1.4930352E7
37: 2.4157817E7
38: 3.9088169E7
39: 6.3245986E7
40: 1.02334155E8
41: 1.65580141E8
42: 2.67914296E8
43: 4.33494437E8
44: 7.01408733E8
45: 1.13490317E9
46: 1.836311903E9
47: 2.971215073E9
48: 4.807526976E9
49: 7.778742049E9
50: 1.2586269025E10
51: 2.0365011074E10
52: 3.2951280099E10
53: 5.3316291173E10
54: 8.6267571272E10
55: 1.39583862445E11
56: 2.25851433717E11
57: 3.65435296162E11
58: 5.91286729879E11
59: 9.56722026041E11
60: 1.54800875592E12
61: 2.504730781961E12
62: 4.052739537881E12
63: 6.557470319842E12
64: 1.0610209857723E13
65: 1.7167680177565E13
66: 2.7777890035288E13
67: 4.4945570212853E13
68: 7.2723460248141E13
69: 1.17669030460994E14
70: 1.90392490709135E14
71: 3.0806152117013E14
72: 4.98454011879265E14
73: 8.06515533049395E14
74: 1.30496954492866E15
75: 2.111485077978055E15
76: 3.416454622906716E15
77: 5.527939700884771E15
78: 8.944394323791488E15
79: 1.447233402467626E16
80: 2.3416728348467744E16
81: 3.7889062373144008E16
82: 6.1305790721611752E16
83: 9.9194853094755776E16
84: 1.60500643816367552E17
85: 2.59695496911123328E17
86: 4.2019614072749088E17
87: 6.7989163763861427E17
88: 1.10008777836610509E18
89: 1.77997941600471936E18
90: 2.8800671943708247E18
91: 4.6600466103755448E18
92: 7.540113804746369E18
93: 1.2200160415121914E19
94: 1.9740274219868283E19
95: 3.19404346349902E19
96: 5.168070885485849E19
97: 8.362114348984869E19
98: 1.3530185234470719E20
99: 2.189229958345559E20
