haskell - 为什么这种斐波那契的实现速度非常快？

Question

斐波那契的这种实现很容易理解，但速度很慢:

fib 0 = 0
fib 1 = 1
fib n = fib (n-1) + fib (n-2)

斐波那契的实现很难理解，但速度非常快。它会立即在我的笔记本电脑上计算出第 100,000 个斐波那契数。

fib = fastFib 1 1

fastFib _ _ 0 = 0
fastFib _ _ 1 = 1
fastFib _ _ 2 = 1
fastFib a b 3 = a + b
fastFib a b c = fastFib (a + b) a (c - 1)

关于后一种实现，这里发生了什么魔力，它是如何工作的？

Answer 1

隐藏输入数字被用作计数器的事实只是混淆。我希望如果你看到这样的东西，你会明白为什么:

fib2 n = fastFib2 0 1 0 n

fastFib2 current previous count 0 = 0
fastFib2 current previous count 1 = 1
fastFib2 current previous count n
  | count == n = current
  | otherwise  =
     fastFib2 (current + previous) current (count + 1) n

在上面的代码中，我们明确了计数器:当它等于我们的输入时，n ，我们返回我们的累加器，current ;否则，我们将跟踪当前和先前数字(“two preceding ones”)的这种“前向”递归，这是构造斐波那契数列所需的一切。

您共享的代码做同样的事情。 (c - 1)使它看起来像一个更传统的“向后”重复，当它实际上是在第一次调用时从累加器开始，然后添加到它。