Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
A better way to recursively solve the Fibonacci sequence
package recursion;
import java.util.function.*;
import static java.lang.System.*;
class Fibonacci {
static long recursions;
public static void main(String[] args) {
for (int i = 30; i < 50; i++) {
testFibCal(i, (n) -> traditionalFib(n));
testFibCal(i, (n) -> improvedFib(n));
}
}
static void testFibCal(int n, IntFunction<Long> fib) {
long start = currentTimeMillis();
recursions = 0;
long result = fib.apply(n);
out.printf("Calculated first %d in the Fibonacci "
+ "sequence in %dms and %d recursions. The result is %d.%n",
n,
currentTimeMillis() - start,
recursions,
result);
}
static long traditionalFib(int n) {
recursions++;
return n <= 1 ? n : traditionalFib(n-1) + traditionalFib(n-2);
}
static long improvedFib(int n) {
return calcFib(n-2, 1, 1);
}
static long calcFib(int n, long a, long b) {
recursions++;
return n-- == 0 ? b : calcFib(n, b, a+b);
}
}
/*
* Output:
*
* Calculated first 30 in the Fibonacci sequence in 6ms and 2692537 recursions. The result is 832040.
* Calculated first 30 in the Fibonacci sequence in 0ms and 29 recursions. The result is 832040.
* Calculated first 31 in the Fibonacci sequence in 8ms and 4356617 recursions. The result is 1346269.
* Calculated first 31 in the Fibonacci sequence in 0ms and 30 recursions. The result is 1346269.
* Calculated first 32 in the Fibonacci sequence in 12ms and 7049155 recursions. The result is 2178309.
* Calculated first 32 in the Fibonacci sequence in 0ms and 31 recursions. The result is 2178309.
* Calculated first 33 in the Fibonacci sequence in 18ms and 11405773 recursions. The result is 3524578.
* Calculated first 33 in the Fibonacci sequence in 0ms and 32 recursions. The result is 3524578.
* Calculated first 34 in the Fibonacci sequence in 30ms and 18454929 recursions. The result is 5702887.
* Calculated first 34 in the Fibonacci sequence in 0ms and 33 recursions. The result is 5702887.
* Calculated first 35 in the Fibonacci sequence in 48ms and 29860703 recursions. The result is 9227465.
* Calculated first 35 in the Fibonacci sequence in 0ms and 34 recursions. The result is 9227465.
* Calculated first 36 in the Fibonacci sequence in 79ms and 48315633 recursions. The result is 14930352.
* Calculated first 36 in the Fibonacci sequence in 0ms and 35 recursions. The result is 14930352.
* Calculated first 37 in the Fibonacci sequence in 127ms and 78176337 recursions. The result is 24157817.
* Calculated first 37 in the Fibonacci sequence in 0ms and 36 recursions. The result is 24157817.
* Calculated first 38 in the Fibonacci sequence in 207ms and 126491971 recursions. The result is 39088169.
* Calculated first 38 in the Fibonacci sequence in 0ms and 37 recursions. The result is 39088169.
* Calculated first 39 in the Fibonacci sequence in 341ms and 204668309 recursions. The result is 63245986.
* Calculated first 39 in the Fibonacci sequence in 0ms and 38 recursions. The result is 63245986.
* Calculated first 40 in the Fibonacci sequence in 548ms and 331160281 recursions. The result is 102334155.
* Calculated first 40 in the Fibonacci sequence in 0ms and 39 recursions. The result is 102334155.
* Calculated first 41 in the Fibonacci sequence in 885ms and 535828591 recursions. The result is 165580141.
* Calculated first 41 in the Fibonacci sequence in 0ms and 40 recursions. The result is 165580141.
* Calculated first 42 in the Fibonacci sequence in 1439ms and 866988873 recursions. The result is 267914296.
* Calculated first 42 in the Fibonacci sequence in 0ms and 41 recursions. The result is 267914296.
* Calculated first 43 in the Fibonacci sequence in 2354ms and 1402817465 recursions. The result is 433494437.
* Calculated first 43 in the Fibonacci sequence in 0ms and 42 recursions. The result is 433494437.
* Calculated first 44 in the Fibonacci sequence in 3793ms and 2269806339 recursions. The result is 701408733.
* Calculated first 44 in the Fibonacci sequence in 0ms and 43 recursions. The result is 701408733.
* Calculated first 45 in the Fibonacci sequence in 6097ms and 3672623805 recursions. The result is 1134903170.
* Calculated first 45 in the Fibonacci sequence in 0ms and 44 recursions. The result is 1134903170.
* Calculated first 46 in the Fibonacci sequence in 9811ms and 5942430145 recursions. The result is 1836311903.
* Calculated first 46 in the Fibonacci sequence in 0ms and 45 recursions. The result is 1836311903.
* Calculated first 47 in the Fibonacci sequence in 15790ms and 9615053951 recursions. The result is 2971215073.
* Calculated first 47 in the Fibonacci sequence in 0ms and 46 recursions. The result is 2971215073.
* Calculated first 48 in the Fibonacci sequence in 25828ms and 15557484097 recursions. The result is 4807526976.
* Calculated first 48 in the Fibonacci sequence in 0ms and 47 recursions. The result is 4807526976.
* Calculated first 49 in the Fibonacci sequence in 41744ms and 25172538049 recursions. The result is 7778742049.
* Calculated first 49 in the Fibonacci sequence in 0ms and 48 recursions. The result is 7778742049.
*/
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment