Fibonacci in Haskell

Viewed 2435

So here's a fibonacci term-calculating function (in Ruby):

def fibfast(n)
  xs = [0,1]
  (n-1).times do |i|
    next_term = xs.sum
    xs[0]=xs[1]
    xs[1]=next_term
   end
   return xs[1]
 end

I am pretty sure it has constant space complexity (its only stored data is in xs), and linear time complexity (it uses one loop to calculate the nth term of the sequence).

My question is, is the function recursive? It uses values that it calculates to do more calculations, but never calls itself. My other question is, how do I get this same time-space compactness in Haskell? Haskell functions I have found either have space complexity greater than O(1), returning an entire list of terms, and/or they have time complexity greater than O(n) because they use the typical recursive definition.

Any thoughts appreciated, thanks!

1 Answers
Related