这里是一个Fibonacci项计算函数(用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
我非常确定它具有恒定的空间复杂度(它唯一存储的数据在xs中),以及线性时间复杂度(它使用一个循环来计算序列的第n个项)。
我的问题是,这个函数是否递归?它使用它计算出的值进行更多的计算,但从未调用自身。我的另一个问题是,如何在Haskell中获得相同的时间-空间紧凑性?我发现的Haskell函数要么具有大于O(1)的空间复杂度,返回整个术语列表,要么具有大于O(n)的时间复杂度,因为它们使用典型的递归定义。
任何想法都会受到赞赏,谢谢!