# Computing Fibonacci numbers the hard way

I suppose we are all familiar with recursive definitions of Fibonacci numbers, e.g.

```    F(0) = 0
F(1) = 1
F(n) = F(n-1) + F(n-2) for n>1
```
The recursive definition is used in programming exposition as an elegant example and as a grim warning. Thus (1):
```    function fibonacci(n)
if (n <= 0) return 0
else if (n == 1) return 1
return fibonacci(n-1)+fibonacci(n-2)
end fibonacci
```
Unfortunately this code blows up; that is, the number of calls grows exponentially. The iterative version uses one call and n cycles through a simple loop. Thus (2):
```    function fibonacci(n)
if (n <= 0) return 0
else if (n == 1) return 1
a = 0; b = 1
do i = 2,n
c = a + b
a = b
b = c
end do
return b
end fibonacci
```
(1) is ‘nicer’ than (2) – it is shorter and has no local variables. Many of the little morals often drawn from this comparison are off the mark; neither form is desirable if we actually want results.

Fibonacci numbers grow exponentially as phi^n. If we want exact results that fit in 32 or 64 bit integers then a lookup table suffices. If we want exact results for larger n, bignums and a more efficient algorithm is indicated. If the result does not have to be exact the asymptotic formula is indicated.

Although the simple recursion is not useful as an implementation it is useful for an entirely different reason – as a simple stress test for other software, e.g., compilers and run time systems.

One place it is particularly useful is in analyzing data flow languages and their implementations. For those not familiar with the data flow paradigm, data flow programs are composed of units variously called light processes, agents, actors, and even modules. In imperative programming functions return data and control to their caller. In dataflow programming agents pass data to their successors. Agents become active when they receive data and become quiescent when their input is exhausted. Here is a data flow version of the recursive fibonacci algorithm.

```    process main
spawn fibonacci
self=>fibonacci=>self
send n
print result
end main
process fibonacci
if (n < 2) send n
else
spawn child1 = fibonacci
spawn child2 = fibonacci
send (child1) n-1
send (child2) n-2
end else
die
end fibonacci