Fibonacci Haskell 实现的问题

发布于 2024-11-18 06:30:25 字数 224 浏览 3 评论 0原文

刚刚开始重新学习 Haskell（在大学学过，但忘记了大部分内容），我想我会首先实现一个斐波那契函数。然而，即使对于非常小的n，我仍然会遇到堆栈溢出。

谁能发现我的功能有什么问题吗？

fib :: Integer -> Integer
fib 0 = 0
fib 1 = 1
fib n = fib (n-1) + fib (n+1)

原文

Just started re-learning Haskell (did it at uni but forgot most of it) and thought I would implement a Fibonacci function to start of with. However, I keep getting a stackoverflow, even for very small n.

Can anyone spot any problems with my function?

fib :: Integer -> Integer
fib 0 = 0
fib 1 = 1
fib n = fib (n-1) + fib (n+1)

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

横笛休吹塞上声 2024-11-25 06:30:25

您的斐波那契公式中有一个错误：

fib :: Integer -> Integer
fib 0 = 0
fib 1 = 1
fib n = fib (n-1) + fib (n-2)

请注意最后一项，其中有 n-2 而不是 n+1。

You have an error in your fibonacci formula:

fib :: Integer -> Integer
fib 0 = 0
fib 1 = 1
fib n = fib (n-1) + fib (n-2)

Note the very last term where there is n-2 instead of n+1.

回复收藏 0 原文

一张白纸 2024-11-25 06:30:25

这是一个非常糟糕的实现，你应该使用尾递归，从 0 或 1 开始向上并传递前两个斐波那契数。还有一个错误，fib n 取决于 fib n+1。

fib :: Integer -> Integer
fib 0 = 0
fib n = iter 0 1 n
  where iter :: Integer -> Integer -> Integer -> Integer
        iter f1 f2 0 = f2
        iter f1 f2 n = iter f2 (f1+f2) (n-1)

It's a very bad implementation, you should use tail recursion, start from 0 or 1 going upwards and passing the previous two fibonacci numbers. Also there is a bug, fib n depends on fib n+1.

fib :: Integer -> Integer
fib 0 = 0
fib n = iter 0 1 n
  where iter :: Integer -> Integer -> Integer -> Integer
        iter f1 f2 0 = f2
        iter f1 f2 n = iter f2 (f1+f2) (n-1)

回复收藏 0 原文

~没有更多了~