Some fun and possibly interesting things about the famous Fibonacci function.
Introduction
The well-known Fibonacci function is commonly used to introduce computer science students to the notion of recursion. This follows naturally from the way in which the function is usually defined:
F(0)<- 0 F(1)<- 1 F(n)<- F(n-1) + F(n-2)
This is good pedagogically for a couple of obvious reasons: it's quite easy to program in much the form shown here in almost any language, and the simple version of the program often performs quite poorly for large values of "n". This leads naturally to the sort of detailed discussions of algorithm performance, "big O" notation and other subjects much beloved by CS professors.
However, perhaps there is an even better lesson to be learned from this example, which is that a linear recurrence like this has a closed-form solution. John Sullivan wrote a short article for Vector years ago, where he derived the closed-form solution in APL, which is where I first heard of it. Actually, it's been known for hundreds of years as Binet's Formula.
The fun thing about this solution is that it opens up completely new avenues for exploration. I've defined this in J as
fibonacci=: 3 : 0"0 b=. - a=: % sqrt5=. %: 5 (a * (-:1+sqrt5) ^ y) + b * (-:1-sqrt5) ^ y )
The big difference between this and the usual implementation is that it is a continuous function. Also, its domain is not restricted to non-negative integers, or even to real numbers. The non-integer solutions are complex numbers. If we treat the real and imaginary parts as (X, Y) pairs and plot them, we get interesting pictures.
Try this:
load 'plot' 'pensize 3' plot fibonacci i:5j99
We get what has been called the "Helmet of Athena", after the goddess of wisdom: 
Note that the result of the fibonacci function applied only to negative numbers gives the familiar logarithmic spiral:
'pensize 3' plot fibonacci -5+i:5j99
Looking at only the positive values, we see this for values from zero to ten: 
Looking more closely at the positive values up to four, we get this 
Notice how the loop allows this function to cross the x-axis twice at x=1; the axis crossings correspond to the values of the Fibonacci function in its more boring form: 0 1 1 2 3....
Here's a much more complete exploration of different ways of implementing the Fibonacci function in J.