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.

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.

Visually 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:

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

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.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 |
public class R { public static void main( String[] a ) { for ( int i = 0; i <= 10; i++ ) { System.out.println( f( i ) ); } } private static int f( int n ) { if ( n <= 1 ) return n; return f( n - 1 ) + f( n - 2 ); } } |

**Using a loop**

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.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
class W { public static void main( final String[] args ) { int a = 0; int b = 1; while ( a < 144 ) { System.out.println( a ); b = a + b; a = b - a; } } } |

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

1 2 3 4 5 6 7 8 9 10 11 12 |
class F { public static void main( final String[] x ) { for ( int a = 0, b = 1; a <= 144; a = b + (b = a) ) { System.out.println( a ); } } } |

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 😉

Recursive Fibonacci Algorithm using Memoization and Dynamic Programming - eonjavaOctober 28, 2015 at 2:20 am[…] first article on Progamming the Fibonaaci Sequence over two years ago referred to a couple of approaches at generating the Fibonacci sequence […]