Fibonacci Numbers

The Fibonacci sequence is

1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, etc.

Notice that after the first two entries, each entry is the sum of the two before it. Therefore we can use divide-and-conquer to implement a function that computes the nth Fibonacci number:

int fib(int n) {
   if (n <= 1) return 1;
   return fib(n – 1) + fib(n – 2);
}

Analysis

Define:

T(n) = # of calls to fib needed to compute fib(n)

Clearly:

T(0) = T(1) = 1

For n > 1:

T(n) = T(n – 1) + T(n – 2)

In other words:

T(n) = fib(n)

Is that good? No:

T(n) > 2T(n – 2) > 4T(n – 4) > 8T(n – 6) > 2^kT(n – 2k)

In n/2 = k, then

T(n) > 2^n/2 = O(2ⁿ)

Dynamic Solution

Let's create a memoized version of the Fibonacci function. Two solutions in Java are the polymorphic solution and the lambda solution. They are similar. Both create a generic class called UnaryMemnoizer<D, R>, where D represents the domain of the function and R represents the range. Instances of this class will contain the cache and the un-memoized function.

In the polymorphic solution the function is a method implemented in a sub-class of UnaryMemoizer. In the lambda solution no sub-class is needed. The function is a field of UnaryMemoizer. (This is only possible in Java 8, which introduces function-objects called lambdas.)

Here's the complete code:

FibTest.java

Here are sample calls with the cache on and then off. Note the dramatic difference:

fib(0) = 1
fib(1) = 1
fib(2) = 2
fib(3) = 3
fib(4) = 5
fib(5) = 8
fib(6) = 13
fib(7) = 21
fib(8) = 34
fib(9) = 55
call count = 10
fib(0) = 1
fib(1) = 1
fib(2) = 2
fib(3) = 3
fib(4) = 5
fib(5) = 8
fib(6) = 13
fib(7) = 21
fib(8) = 34
fib(9) = 55
call count = 276

In fact, T(n) = n when the cache is on. The down side is memory usage. Let

M(n) = memory used by a call to fib(n)

With the cache on M(n) = O(n²) with it off M(n) = O(2n).

For those interested, the lambda solution can be found here:

LambdaFibTest.java

Iterative Solution

Of course the old fashion iterative approach out-performs both the cached and un-cached solutions:

int fib(int n) {
   int fib1 = 1;
   int fib2 = 1;
   for(int i = 0; i < n; i++) {
      int temp = fib1;
      fib1 = fib2;
      fib2 = temp + fib1;
   }
   return fib2;
}

It's easy to see that:

T(n) = O(n)
M(n) = O(1)