在Haskell中的斐波那契数列

Question

这里是一个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）的时间复杂度，因为它们使用典型的递归定义。

任何想法都会受到赞赏，谢谢！

- Zachary Bechhoefer

---

为什么递归定义会具有更高的时间复杂度？ - Willem Van Onsem

递归定义的斐波那契函数需要更多的计算，我相信它的复杂度是O(2^n)。 - Zachary Bechhoefer

是的，使用累加器通常对尾递归优化很有好处，但如果选择得当，它也可以减少时间复杂度。 - Willem Van Onsem

相关链接：https://wiki.haskell.org/The_Fibonacci_sequence - Alec

如果同时从迭代转换为递归，并且从该标准算法转换为朴素算法，则确实会得到 O(fib(n)) 时间复杂度。但是，仅仅改变从迭代到递归的风格——同时保持相同的算法——将保持相同的 O(n) 时间复杂度。 - Daniel Wagner

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 来存储序列中的最后两个值。每次迭代时，这两个值都会更新，并且我们会减少要执行的迭代次数，直到达到小于等于 1 的数字 n 为止，在这种情况下，我们将返回第二个累加器。

问题在于，Haskell 通常不会急切地计算表达式，而是以惰性的方式存储 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)

- Willem Van Onsem

---

非常酷！你是在特定的课程中学习这个的吗？比如算法设计之类的？谢谢！ - Zachary Bechhoefer

@ZacharyBechhoefer：不是的。实际上，我最初是在逻辑编程课程（Prolog）中学习累加器的。但是逻辑和函数式编程有一些共同的背景。 - Willem Van Onsem

@ZacharyBechhoefer 这个（我相信还有其他地方）是在《计算机程序的构造和解释》（Structure and Interpretation of Computer Programs，简称SICP）中早期所教授的。它实际上将斐波那契作为示例程序，比较迭代与递归过程和进程之间的差异。 - Mulan