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!