# Fibonacci Functions

## DeWitt ClintonMay 2008

Tim Bray recently wrote in a short post entitled Language-Book Principles:

I am getting really, really bored with factorial and Fibonacci algorithms. It is really remarkably infrequent that I implement any code that looks much like either.

To which I responded:

Ah, but they do matter! You can tell a *lot* about how a language works by looking at those simple examples. Does it encourage and/or optimize for tail-recursion? Does the language use strong typing / type annotations / type inference? Parameter pattern matching? Does it feel functional vs. imperative? Compare a Fibonacci implementation in Lisp to ML to C to Java to Scala and the differences are immediately apparent.

Here are some examples, courtesy of LiteratePrograms, slightly modified by me in a few cases. Any bugs introduced are my fault entirely, I'm sure.

A trivial, elegant, and painfully overflowing recursive implementation in C:

```unsigned int fib(unsigned int n)
{
return n < 2 ? n : fib(n-1) + fib(n-2);
}```

Again in C, but using iteration instead of recursion:

```unsigned long fib(unsigned long n)
{
unsigned long f0 = 0;
unsigned long f1 = 1;
unsigned long result = 0;
if (n == 0) return 0;
while (n--) {
result = f1;
f1 = f0 + f1;
f0 = result;
}
return result;
}```

A tail recursive Fibonacci generator in Lisp:

```(defun fib-trec (n)
(labels ((calc-fib (n a b)
(if (= n 0)
a
(calc-fib (- n 1) b (+ a b)))))
(calc-fib n 0 1)))```

(GNU Clisp 2.43 on my OSX box evals `(fib-trec 5000)` instantly, so I guess it must be optimizing the tail call.)

A marginally cleaner but otherwise identical version in Scheme:

```(define (fib n)
(letrec ((fib-aux (lambda (n a b)
(if (= n 0)
a
(fib-aux (- n 1) b (+ a b))))))
(fib-aux n 0 1)))```

A succinct and iterative approach in Python:

```def fib(n):
a, b = 0, 1
for i in xrange(n):
a, b = b, a + b
return a```

The same idea, but using generators:

```def fib():
a, b = 0, 1
while True:
a, b = b, a + b
yield a```

And again in Python, this time using memoization:

```def fib(n):
memo = {0:0, 1:1}
if not n in memo:
memo[n] = fib(n-1) + fib(n-2)
return memo[n]```

(You can move the declaration of `memo` to speed it up on successive calls.)

A limited precision (32 or 64 bit) implementation in OCaml:

```let rec i_fib a b = function
| 0 -> a
| 1 -> b
| k when k > 1 -> i_fib b (a+b) (k-1)
| _  -> raise (Invalid_argument)
```

(If you don't like the ML then you have no soul.)

Same thing, this time in Haskell:

```fib :: Integer -> Integer
fib 0 = 0
fib 1 = 1
fib n = fib (n-1) + fib (n-2)```

(Can you tell I'm a fan of parameter pattern matching and type annotation/inference?)

A very pretty tail recursive implementation in Scala:

```def fib(n:Int) = fib_tr(n, 1, 0)

def fib_tr(n: Int, b: Int, a: Int): Int = n match {
case 0 => a
case _ => fib_tr(n-1, a + b, b)
}```

(Okay, I may have just fallen in love with Scala.)

And lastly, for Tim, a fast implementation in Erlang:

```fibo3(N) ->
{Fib, _} = fibo3(N, {1, 1}, {0, 1}),
Fib.

fibo3(0, _, Pair) -> Pair;
fibo3(N, {Fib1, Fib2}, Pair) when N rem 2 == 0 ->
SquareFib1 = Fib1*Fib1,
fibo3(N div 2, {2*Fib1*Fib2 - SquareFib1, SquareFib1 + Fib2*Fib2}, Pair);
fibo3(N, {FibA1, FibA2}=Pair, {FibB1, FibB2}) ->
fibo3(N-1, Pair, {FibA1*FibB2 + FibB1*(FibA2 - FibA1), FibA1*FibB1 + FibA2*FibB2}).```

I see great beauty in all* of these.

*Well, except for the Erlang, which I find to be pathological.