Growing with the Web

The Fibonacci sequence

Published , updated
Tags:

This article looks at the interview question - Implement a function that returns the Fibonnaci number for a given integer input.

Analysis

The Fibonacci sequence is the recurrence defined as

f(n) = f(n - 1) + f(n - 2)
\text{where }f(0) = 0\text{ and }f(1) = 1

Or in simpler terms, it’s the sequence of numbers starting with 0 and 1 that is constructed by adding the previous 2 numbers together. Here are numbers 0 through 15:

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, …

Recursive

A sequence of numbers that can be defined with a recurrence can be very easily translated into a recursive function. Remember though that while the solution may be elegant, it can also be unsuitable if the input is sufficiently large. Many recursive calls quickly add up and can lead to a stack overflow exception.

A primitive solution to give the Fibonnaci number for a particular input is to simply define the base cases (f(0) and f(1)) and then call into itself. The major flaw with this is that calling f(10) will call f(9) and f(8) which in turn will f(8), f(7), f(7) and f(6), and so on… At each call we are doubling the amount of work to be done (ie. it’s growing exponentially), most of which has already been done.

This function can be optimised by applying dynamic programming to the solution, which is basically a fancy name for caching results from smaller problems and using them to solve a bigger problem. So when f(x) is called we will store the result before returning it, so when it is called again with the same input there is no need to recurse all the way down to f(0) and f(1) again.

Iterative

For an iterative solution, the function can keep track of two numbers starting with f(0) and f(1), then iterate over them, continually incrementing their input numbers each iteration until the number is found. So the first time through the loop we swap the first value f(0) with the second (f(1)), and then set the second value to the original value in first and second (f(0) + f(1)), which would result in the values f(1) and f(2).

Pseudocode

Recursive

fib(n)
  if (n < 0)
    throw
  if (n == 0)
    return 0
  if (n == 1)
    return 1
  return fib(n-1) + fib(n-2)

fib-v2(n)
  if (n < 0)
    throw
  if (n == 0)
    return 0
  if (n == 1)
    return 1
  if (n in hashtable)
    return hashtable[n]

  value ← fib-v2(n-1) + fib-v2(n-2)
  store value in hashtable
  return value

Iterative

fib-iter(n)
  if (n < 0)
    throw
  if (n == 0)
    return 0
  if (n == 1)
    return 1

  first ← 0
  second ← 1
  counter ← 1

  while counter < n
    temp ← first
    first ← second
    second ← temp + first
    counter ← counter + 1

  return second

Complexity

The original recursive function is exponential O(n^2), while the enhanced recursive solution and the iterative solution both run in linear time O(n).

Code

public static int fib(int n) {
    if (n < 0)
        throw new IllegalArgumentException("n must be >= 0");
    if (n == 0)
        return 0;
    if (n == 1)
        return 1;

    return fib(n - 1) + fib(n - 2);
}

public static int fibV2(int n) {
    return fibV2(n, new HashMap<Integer, Integer>());
}

private static int fibV2(int n, HashMap<Integer, Integer> hash) {
    if (n < 0)
        throw new IllegalArgumentException("n must be >= 0");
    if (n == 0)
        return 0;
    if (n == 1)
        return 1;
    if (hash.containsKey(n))
        return hash.get(n);

    int value = fibV2(n - 1, hash) + fibV2(n - 2, hash);
    hash.put(n, value);
    return value;
}

public static int fibIter(int n) {
    if (n < 0)
        throw new IllegalArgumentException("n must be >= 0");
    if (n == 0)
        return 0;
    if (n == 1)
        return 1;

    int first = 0;
    int second = 1;
    int counter = 1;
    int temp;

    while (counter < n) {
        temp = first;
        first = second;
        second = temp + first;
        counter++;
    }

    return second;
}
function fibonacciRecursive(n) {
  if (n < 0)
    throw 'n must be >= 0';
  if (n === 0)
    return 0;
  if (n === 1)
    return 1;

  return fibonacciRecursive(n - 1) + fibonacciRecursive(n - 2);
}

function fibonacciOptimised(n, map) {
  if (n < 0)
    throw 'n must be >= 0';
  if (n === 0)
    return 0;
  if (n === 1)
    return 1;
  if (!map)
    map = {};
  if (!map[n])
    map[n] = fibonacciOptimised(n - 1, map) + fibonacciOptimised(n - 2, map);

  return map[n];
}

function fibonacciIterative(n) {
  if (n < 0)
    throw 'n must be >= 0';
  if (n === 0)
    return 0;
  if (n === 1)
    return 1;

  var first = 0;
  var second = 1;
  var counter = 1;
  var temp;

  while (counter < n) {
    temp = first;
    first = second;
    second = temp + first;
    counter++;
  }

  return second;
}

Textbooks

Here are two textbooks that provide many Q&A's like this post that I personally recommend, both were invaluable to me when I was studying for my interviews.

 

Comments

comments powered by Disqus
Like this article?
Subscribe for more!