>>8

A recursive haskell fibonacci function that runs in linear time:

[code]fibs = 0 : 1 : (zipWith (+) fibs (tail fibs))[/code]

ta da!