Fibonacci的这种实现很容易理解但很慢：
fib 0 = 0
fib 1 = 1
fib n = fib (n-1) + fib (n-2)
实施Fibonacci之后很难理解，但速度非常快。它会立即在我的笔记本电脑上计算出第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)
关于后一种实施，这里发生了什么神奇的事情，它是如何运作的？
好吧它很慢，因为每次调用fib可能会导致最多两个（平均值更像1.6）调用fib，所以计算fib 5你称为fib 4和fib 3分别调用fib 3和fib 2，以及fib 2和fib 1，所以我们可以看到每次调用fib (n+1)都会产生两倍于调用fib n的工作量。
我们可能观察到的一件事是，我们多次尝试同样的事情，例如以上我们两次研究fib 3。如果你不得不解决这个问题可能需要很长时间。 fib 100两次。
我认为从这开始比试图直接进入fastFib更好。如果我要求你手动计算第十个Fibonacci数，我希望你不会通过应用算法计算第三个数十次。你可能还记得你到目前为止所拥有的东西。事实上，人们可以在Haskell中为此做到这一点。只需编写一个程序来生成Fibonacci数字列表（懒惰）并将其编入索引：
mediumFib = (\n -> seq !! n) where
seq = 0:1:[mediumFib (i-1) + mediumFib (i-2)| i <- [2..]]
这要快得多，但它很糟糕，因为它使用大量内存来存储Fibonacci数列表，并且找到列表的第n个元素很慢，因为你必须遵循很多指针。
从头开始计算单个Fibonacci数（即没有任何已计算的数）需要二次时间。
另一种可以手动计算第十个Fibonacci数的方法是写下Fibonacci序列，直到你到达第十个元素。然后，你永远不需要在过去看远，或者记住你之前计算过的所有东西，你只需要看看前两个元素。可以想象一个必要的算法来做到这一点
fib(n):
if (n<2) return n
preprevious = 0
previous = 1
i = 2
while true:
current = preprevious + previous
if (i = n) return current
preprevious, previous = previous, current
这只是逐步通过递归关系：
f_n = f_(n-2) + f_(n-1)
实际上我们也可以在Haskell中编写它：
fastFib n | n < 2 = n
| otherwise = go 0 1 2 where
go pp p i | i = n = pp + p
| otherwise = go p (pp + p) (i + 1)
现在速度非常快，我们可以将其转换为您拥有的功能。以下是步骤：
pp（preprevious）和p（上一个）的参数顺序i，从n开始倒计时。go提取到顶级函数，因为它不再依赖于n。这个算法只需要在每一步中做一个和，所以它是线性时间，而且非常快。计算fib (n+1)只是计算fib n的一个小常数。将此与上述相比，它大约是工作量的1.6倍。
fib？当然有。事实证明，有一种聪明的方式来表达Fibonacci序列。我们认为转换a,b -> a+b,a是一个转换家族T_pq的一个特例：
T_pq : a -> bq + aq + ap
b -> bp + aq
具体来说，这是p = 0和q = 1的特殊情况。我们现在可以做一些代数来解决，如果有一种简单的方法表达两次应用T_pq：
T_pq T_pq :
a -> (bp + aq)q + (bq + aq + ap)(q + p)
b -> (bp + aq)p + (bq + aq + ap)q
=
a -> (b + a)(q^2 + 2pq) + a(q^2 + p^2)
b -> b(q^2 + p^2) + a(q^2 + 2pq)
= T_(q^2 + p^2),(q^2 + 2pq)
所以现在让我们编写一个简单的函数来计算T_pq^n (a,b)和fib n
tPow p q a b n | n = 1 = (b*q + a*q + a*p, b*p + a*q)
| otherwise = let (a', b') = tPow p q a b 1 in tPow p q a' b' (n-1)
fib 0 = 0
fib 1 = 1
fib n = fst $ tPow 0 1 1 0 (n-1)
现在我们可以使用我们的关系使tPow更快：
tPow p q a b n | n = 1 = (b*q + a*q + a*p, b*p + a*q)
| odd n = let (a', b') = tPow p q a b 1 in tPow p q a' b' (n-1)
| even n = tPow (q*q + p*p) (q*q + 2*p*q) a b (n `div` 2)
为什么这会更快？嗯，它更快，因为计算fib (2*n)只是一个小的常数工作比计算fib n，而在它之前的工作量是工作量的两倍，之前它是工作量的四倍，在此之前它是工作量的平方。实际上，步骤的数量类似于二进制中的n的位数加上1的二进制表示中的ns的数量。计算fib 1024只需要大约10步，而之前的算法大约需要1000步。计算第十亿个Fibonacci数只需要30步，这远远不到10亿步。
神奇的是反射，具体化，计算过程的解释由递归公式描述：
fib 0 = 0 -- NB!
fib 1 = 1
fib n = fib (n-1) + fib (n-2)
-- n1 n2
= let {n1 = fib (n-1) ; n2 = fib (n-2)}
in n1 + n2
= let {n1 = fib (n-2) + fib (n-3) ; n2 = fib (n-2)}
-- n2 n3
in n1 + n2
= let {n1 = n2+n3 ; n2 = fib (n-2) ; n3 = fib (n-3)}
in n1 + n2
= let {n1 = n2+n3 ; n2 = fib (n-3) + fib (n-4) ; n3 = fib (n-3)}
-- n3 n4
in n1 + n2
= let {n1 = n2+n3 ; n2 = n3+n4 ; n3 = fib (n-3) ; n4 = fib (n-4)}
in n1 + n2
= let {n1 = n2+n3 ; n2 = n3+n4 ; n3 = n4+n5 ; n4 = fib (n-4) ; n5 = fib (n-5)}
in n1 + n2
= .......
看到它到最后的情况，然后翻转时间箭头（或者只是从右到左阅读），并明确编码let内部隐含的内容，作为递归的模拟“调用堆栈”操作的一部分。
最重要的是，用等号替换等号，即参考透明度 - 使用n2代替fib (n-2)的每个外观等。
只是想明确一点，尾递归与第二个程序的快速无关。下面，我重写你的第一个程序以使用正确的尾调用，并将执行时间与第二个程序进行比较。我还重写了那个，因为它可以简化一点 -
fib1 n = slow n id
where
slow 0 k = k 0
slow 1 k = k 1
slow n k = slow (n - 1) (\a ->
slow (n - 2) (\b ->
k (a + b)))
fib2 n = fast n 0 1
where
fast 0 a _ = a
fast n a b = fast (n - 1) b (a + b)
像n = 10这样对微小数字的影响可以忽略不计 -
fib1 10
-- 55
-- (0.01 secs, 138,264 bytes)
fib2 10
-- 55
-- (0.01 secs, 71,440 bytes)
但即使在n = 20附近，我们也注意到fib1表现的巨大下降 -
fib1 20
-- 6765
-- (0.70 secs, 8,787,320 bytes)
fib2 20
-- 6765
-- (0.01 secs, 76,192 bytes)
在n = 30，影响是可笑的。两个程序仍然得到相同的结果，所以这很好，但fib1需要超过30秒。 fib2仍然只需要几分之一秒 -
fib1 30
-- 832040
-- (32.91 secs, 1,072,371,488 bytes) LOL so bad
fib2 30
-- 832040 (0.09 secs, 80,944 bytes)
这是因为第一个程序fib1进行了两次递归调用。当n增长时，此函数的过程使用指数时间和空间。在n = 30，慢速程序将进行1,073,741,824（230）个递归调用。快速程序只会重复30次。
在n = 1000，我们遇到了fib1的严重问题。根据fib1 30的表现，我们估计需要1.041082353242204e286年才能完成21000个递归调用。同时，fib2 1000毫不费力地处理1000次递归 -
fib2 1000
-- 43466557686937456435688527675040625802564660517371780402481729089536555417949051890403879840079255169295922593080322634775209689623239873322471161642996440906533187938298969649928516003704476137795166849228875
-- (0.13 secs, 661,016 bytes)
使用添加的k参数可能难以遵循第一个程序的原始重写。使用Cont让我们可以看到Haskell熟悉的do表示法中的一系列清晰步骤 -
import Control.Monad.Cont
fib1 n = runCont (slow n) id
where
slow 0 = return 0
slow 1 = return 1
slow n = do
a <- slow (n - 1)
b <- slow (n - 2)
return (a + b)
隐藏输入数字用作计数器这一事实只是模糊处理。我希望如果你看到这样的东西，你会理解为什么：
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”）的“向前”递归，这是构建Fibonacci序列所需的全部内容。
您共享的代码也是一样的。 (c - 1)使它看起来像一个更传统的“向后”重复，当它实际上在第一次调用中从累加器开始，然后添加到它。