Sep
28
2013

Programming the Fibonacci Sequence

I have to admit I had no idea who “Fibonacci” was when I interviewed for a programming position at Zappos in Las Vegas over six years ago.

I do now.

fibonacci_portrait

Leonardo Fibonacci c1175-1250

Apparently over around the year 1202, an Italian mathematician, Leonardo Pisano Bigollo (also known as Fibonacci), was trying to determine how fast rabbits could breed under an ideal set of circumstances.

One pair of rabbits (1 pair) would be born and after one month reach sexual maturity and mate (still just 1 pair).  After a one month gestation period, they would give birth to another pair (now there are 2 pair) and mate again.  After three months, the original pair gives birth again while their spawn mate (now we have 3 pair).

Under this fictional scenario, the number of pairs of rabbits in the field at the start of each month turned out to be 1, 1, 2, 3, 5, 8, 13, 21, 34, and so on.  The rate of growth (or distance between numbers in the set) increases over time.  Using this algorithm, you could determine the next number in the series by adding the previous two numbers:  1+1 = 2, 2 + 1 = 3, 3 + 2 = 5, and so on.

FibonacciVisually you could imagine placing blocks together whose width and height match each number in the Fibonacci sequence.  Two blocks are 1×1.  The next block is 2×2, then 3×3, then 5×5 and so on.

If you were to draw a series of connected quarter-circles within each block a resulting logarithmic spiral occurs that is a very close approximation to the geometric pattern known as the “golden spiral” and the ratio at which each quarter turn grows is a very close approximation to the “golden ratio” (or Phi, φ).   The golden ratio (otherwise known as the “divine proportion”) and golden spiral have been often found in nature, architecture and art throughout history.

Anyway, without digging too deep into the mathematics behind the golden spiral, creating programming instructions that will print out the Fibonacci sequence is a common software interview question to which there are several differing solutions.  I’ll present two of them here.

Recursion 

Recursive Fibonacci sequence generators are great examples.   They show a programmer’s ability to grasp the idea of recursion.

►  A recursive function is a procedure or sub-routine that calls itself.

The Fibonacci sequence itself in mathematical terms is a recurrence relation.  It can be defined by this equation:

equation

Let’s convert this equation to a format programmer’s are more used to seeing.

Fibonacci Equation as a function call

In this case, “f” is just a function that takes an integer as an argument.  Inside this function is the operation above.  As you can see, the function would call itself, but during each loop or recursion, the value of the argument (n) is decremented by one and two (remember the next value in the Fibonacci sequence is the previous number, n-1, and the previous previous number, n-2).

Obviously the value of (n) will eventually get down to one or zero.  The Fibonacci sequence demands that the first two integers are zero and one.  So clearly once the value of (n) gets down to those values we’ll need a conditional in place to just “break” the loop (return in this case since it’s a function).

Let’s use this above equation as the core operation to our Fibonacci method.  We’ll call this Fibonacci method from our Java program’s main method (remember, static main methods can only call static functions).  We’ll add a conditional if-statement to serve as our stopping point.

Using a loopslide

In Java, this same operation can be performed using a while loop.

Since the next value in any Fibonacci sequence is the sum of the previous two values, we need place-holders for those values (a) and (b).  We logically increment these values to “slide” the variables across the sequence of numbers as illustrated in this diagram.

Imagine sliding (b) into the next numerical value in the sequence.  The equation to determine the next value is easy since it’s always the sum of the previous two values (b = a + b).  Determining the value of (a) after that is fairly straight-forward.

You could also use a for-loop.  The example below shows the shortest possible solution, although it may be considered bad form.

Armed with these various examples and the concept behind generating the Fibonacci sequence, you should be able to breeze through this question should it come up in your next interview 😉

About the Author: Erich Cervantez

1 Comment+ Add Comment

Leave a comment

%d bloggers like this: