Fibonacci Numbers: Difference between revisions

From NovaOrdis Knowledge Base
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:

Dynamic Programming