Haskell的斐波那契

Question

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

有任何想法,谢谢!

Answer 1

我的问题是,函数是递归的吗？它使用它计算的值来进行更多计算,但从不调用自身.

否:递归意味着某些东西是根据自身定义的.该fibfast功能本身并未定义.

我的另一个问题是,如何在Haskell中获得相同的时空紧凑性？我发现Haskell函数的空间复杂度大于O(1),返回整个术语列表,和/或它们的时间复杂度大于O(n),因为它们使用典型的递归定义.

您可以使用以下功能:

fibfast :: Int -> Int
fibfast n = fib' 0 1 n
    where fib' a b n | n <= 1 = b
                     | otherwise = fib' b (a+b) (n-1)

所以在这里我们定义一个递归函数fib'并使用两个累加器a并b存储序列中的最后两个值.每次迭代,两次都会更新,我们会减少我们必须进行的迭代次数,直到它达到n小于或等于的数字为止,1在这种情况下我们返回第二个累加器.

问题可能是Haskell通常不会急切地评估表达式,而是懒惰地评估表达式.所以它存储a+b而不是计算a+b.结果表达树很快就会像a+b+a+b+a+b...,因此迅速增长.例如,我们可以使用爆炸模式:

{-# LANGUAGE BangPatterns #-}

fibfast :: Int -> Int
fibfast n = fib' 0 1 n
    where fib' a !b !n | n <= 1 = b
                       | otherwise = fib' b (a+b) (n-1)