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

我很确定它具有常量 space 复杂度（它唯一存储的数据在 xs 中）和线性时间复杂度（它使用一个循环来计算序列的第 n 项）。

我的问题是，这个函数是递归的吗？它使用它计算的值来进行更多计算，但从不调用自己。我的另一个问题是，我如何在 Haskell 中获得同样的时间-space 紧凑性？ Haskell 我发现的函数 space 复杂度大于 O(1)，返回整个术语列表，and/or 它们的时间复杂度大于 O(n)，因为它们使用典型的递归定义。

任何想法表示赞赏，谢谢！

Answer 1

My question is, is the function recursive? It uses values that it calculates to do more calculations, but never calls itself.

否：递归意味着某些东西是根据自身定义的。 fibfast 函数本身没有定义。

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.

您可以使用以下功能：

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 在这种情况下我们 return 第二个累加器.

一个问题可能是 Haskell 通常不会急切地评估表达式，而是 懒惰地 。所以它存储a+b而不是计算a+b。结果，表达式树很快就会像 a+b+a+b+a+b...，从而快速增长。例如，我们可以使用 bang patterns:

{-# 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)

Haskell 中的斐波那契数列

Fibonacci in Haskell

recursion

complexity-theory

haskell

fibonacci