我正在学习Haskell,并编写了一个简单的斐波那契函数:
fib :: Int -> Int
fib 1 = 1
fib 0 = 0
fib n = (fib (n-1)) + (fib (n-2))
看起来编译没问题,将这个脚本加载到GHCI REPL中,我可以尝试一些数字操作。 我试过了。
fib 33
我曾经试着用Haskell编写Fibonacci数列并测试了一下,结果发现计算结果需要约4秒钟的时间(很抱歉我还不知道如何在Haskell中计时函数,所以我自己计数了)。
Fibonacci数列的第33项并不是特别复杂,答案小于400万。因此,我认为我的代码可能写得不太好,或者可能存在递归方式的问题(实际上,我的代码没有考虑到负整数)。问题在于,为什么它运行得这么慢呢?任何帮助都将不胜感激。
fib(5)
被计算的频率。每次迭代,您都会重新计算所有“内部”的斐波那契数。 - WeStfibs = 0 : 1 : zipWith (+) fibs (tail fibs)
,其中fib n = fibs!!n
。请参阅关于斐波那契数列的 Haskell Wiki。有趣的是,斐波那契因这个序列而闻名,但实际上这只是他所著书籍中介绍西欧位值的一个小练习。 - AndrewC