Fibonacci and pineapples

The Fibonacci sequence is found in the strangest of places. Take pineapples for example. The number of spiral rows of fruitlets (eyes) in pineapples was study as early as 1933 in an article by Linford [1] published in Pineapple Quarterly, however no reference was made to Fibonacci numbers. In a follow-up study by Onderdonk [2] in 1970 it was found that the majority of pineapples had 8-13-21 rows of fruitlets, with a few smaller ones at 5-8-13. It was suggested that a pineapple with more fruitlets for a given size would have a finer texture, and it was hoped that a pineapple with 13-21-34 rows could be found, however Onderdonk never found any pineapples exhibiting such a pattern. In general, pineapples have three series of spirals, derived from the roughly hexagonal pattern of its fruitlets, or scales.

Here is an example of the hexagonal scale patterns found on a pineapple.

[1] Linford, M.B., “Fruit quality studies II. Eye number and eye weight”, Pineapple Quarterly, 3, pp.185-188 (1933)
[2] Onderdonk, P.B., “Pineapples and Fibonacci numbers”, The Fibonacci Quarterly, 8(5), pp.507-508 (1970)

Why calculating Fibonacci using binary recursion is just plain moronic

The Fibonacci sequence is a series of numbers of the form:

0, 1, 1, 2, 3, 5, 8, 13, 21, 34,…

It is derived such that each number is the sum of the two preceding ones, starting from F(0)=0 and F(1)=1. Or in equation form: F(n) = F(n-1) + F(n-2).

The original formula for the Fibonacci series lends itself to a natural, if somewhat naïve, example of binary recursion, which is probably the most notorious implementation found in the literature. The algorithm works by returning one if n = 1 or 2, and the sum of  f(n-1)  and f(n-2) if n>2 . Represented as a recursive function in C, this looks like:

int fib_binary(int n) {
   if (n == 0)
      return 0;
   else if (n == 1)
      return 1;
   else
      return fib_binary(n-1) + fib_binary(n-2);
}

This algorithm certainly generates the correct answer, but what is its computational cost, i.e. how long does it take?  If n is less than two, the function halts almost immediately. However for larger values of n, there are two recursive calls of the algorithm. This implies that the running time of the algorithm grows at exponential time, or f(n)=2^0.694n, which for n=200 is 2^140 operations. 

To understand how this is possible, consider the Fibonacci call tree for calculating the 5th Fibonacci number, which just happens to be 5. Notice how many times F₁ is called?

fibonacci_tree

The biggest problem with using binary recursion to calculate the Fibonacci numbers is the time spent re-calculating already calculated Fibonacci numbers. For example, when calculating f(40) using recursion, f(39) is calculated once,  f(35) is calculated 8 times, f(1) is calculated 102,334,155 times, and  f(0) is calculated 63,245,986 times. All up there is a total of 331,160,281 function calls. The calculation of f(40) actually takes an average of 900 milliseconds (on my MacBook Pro with a 2.9 GHz Intel Core i5).

This is an interesting analysis, rarely made in textbooks. Few textbooks discuss alternatives to binary recursion for Fibonacci. Indeed, the use of Fibonacci numbers to illustrate binary recursion is a good example of when not to use recursion.

For anyone interested in Fibonacci numbers, there is a whole journal available online, The Fibonacci Quarterly.

Generating a recursive Romanesco broccoli

Romanesco broccoli is an edible flower of the species Brassica oleracea which includes cabbage, broccoli, Brussel sprouts, cauliflower, collard greens, and numerous other “cultivars”. It was first documented in Italy (as broccolo romanesco) in the sixteenth century. In French it is known as chou Romanesco, which translates to “Romanesco cabbage”, but it is by no means a cabbage. The Germans call it Pyramidenblumenkohl, or “pyramid cauliflower”. Romanesco broccoli is what could be termed a self-similar vegetable. There are vegetables which are composed of smaller copies of themselves ad infinitum, or at least until some limit where the similarity breaks down.

Equiangular spirals (also known as logarithmic spiral, Bernoulli spiral, and logistique) describe a family of spirals. It is defined as a curve that cuts all radii vectors at a constant angle.

How do we build a visualization of this vegetable? In Processing of course! Here is the Processing code to generate the Romanesco broccoli. The first piece of code handles setting up the Processing environment, and defining constants like the Golden ratio, the number of florets. It also sets up the Processing draw() function, which executes drawRomanesco(), and takes a snapshot of the final picture.

The remainder of the code deals with the function drawRomanesco() [1].

This is a nice recursive function, which as the base case draws a circle, using the function ellipse(). The recursive case, sets up some parameters, then uses a loop to derive the florets, which internal to the loop, recursively calls itself. The depth of the Romanesco is controlled by the number of levels, which in the case of the example above is 3. The first level is the overall Romanesco with 60 florets, the second level builds each of 60 florets within those florets, and the third level builds the florets within the florets, within the florets. The resulting image of the Romanesco broccoli, is below, showing the Romanesco from above. Of course it is not perfect, because the florets on the real Romanesco are angled out from the main axis.

[1] Code derived from algorithm on http://joyofprocessing.com.