小编Zac*_*fer的帖子

所以这是一个斐波纳契术语计算函数(在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),因为它们使用典型的递归定义.

有任何想法,谢谢!