Fibonacci Functions

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.