Fibonacci Numbers: Difference between revisions
Jump to navigation
Jump to search
| Line 18: | Line 18: | ||
φ=1.6180339... | φ=1.6180339... | ||
=Algorithms= | |||
==Straightforward Recursive== | |||
A straightforward recursive algorithm looks like this: | |||
<syntaxhighlight lang='java'> | |||
public static long fib(long n) { | |||
if (n == 0) { | |||
return 0; | |||
} | |||
if (n == 1) { | |||
return 1; | |||
} | |||
return fib(n - 1) + fib(n - 2); | |||
} | |||
</syntaxhighlight> | |||
However, the running time of this method, computed with a recursion tree, is O(2<sup>n</sub>): | |||
This is a bad exponential time, and attempting to use the algorithm for anything larger than 50 gets problematic. The solution is to apply a [[#Dynamic_Programming|dynamic programming]] method: | |||
==Dynamic Programming== | |||
Revision as of 21:36, 11 November 2021
Internal
Overview
We define Fibonacci numbers by the following recurrence:
F0 = 0
F1 = 1
Fi = Fi-1 + Fi-2 for i ≥ 2.
TODO CLRS page 108.
Golden Ratio
φ=1.6180339...
Algorithms
Straightforward Recursive
A straightforward recursive algorithm looks like this:
public static long fib(long n) {
if (n == 0) {
return 0;
}
if (n == 1) {
return 1;
}
return fib(n - 1) + fib(n - 2);
}
However, the running time of this method, computed with a recursion tree, is O(2n):
This is a bad exponential time, and attempting to use the algorithm for anything larger than 50 gets problematic. The solution is to apply a dynamic programming method: