Indeed! In fact, it occurs to me that you can get something of a 'best of both worlds' solution between the elegant mathematical solution and the exactness of the recursive solution very easily in Haskell, by defining the field extension* Q(√5), i.e. the rational numbers extended with the square root of 5

  import Data.Ratio
  
  -- The number (a :+ b) represents (a + b √5)
  data Q5 = Rational :+ Rational deriving (Show) 

  instance Num Q5 where
    (a :+ b) + (c :+ d) = (a + c) :+ (b + d)
    (a :+ b) * (c :+ d) = (a * c + 5 * b * d) :+ (a * d + b * c)

  phi = (1 % 2) :+ (1 % 2)

It's now enough to notice that the coefficient of √5 in phi^n is half the n'th fibonacci number, so define

  fib n = let a :+ b = phi^n in round (2 * b)

to get

  >> fib 10
  55
  >> fib 20
  6765
  >> fib 80
  23416728348467685 -- exact result in O(log n)!

* http://en.wikipedia.org/wiki/Field_extension