我该如何编写这个 Clojure 函数才不会耗尽堆栈？
我是 Clojure 的新手，我认为到目前为止我编写代码的方法不符合“Clojure 之道”。至少，我一直在编写一些函数，这些函数不断导致值较大的 StackOverflow 错误。我已经了解了如何使用 recur，这是向前迈出的一大步。但是，如何使像下面这样的函数适用于 2500000 这样的值呢？
(defn fib [i]
(if (>= 2 i)
1
(+ (fib (dec i))
(fib (- i 2)))))
在我看来，该函数是斐波那契生成器的“简单”实现。我见过其他更优化的实现，但就其功能而言不太明显。即，当您阅读函数定义时，您不会说“哦，斐波那契”。
任何指示将不胜感激！
I'm new to Clojure and I think my approach to writing code so far is not in line with the "Way of Clojure". At least, I keep writing functions that keep leading to StackOverflow errors with large values. I've learned about using recur which has been a good step forward. But, how to make functions like the one below work for values like 2500000?
(defn fib [i]
(if (>= 2 i)
1
(+ (fib (dec i))
(fib (- i 2)))))
The function is, to my eyes, the "plain" implementation of a Fibonacci generator. I've seen other implementations that are much more optimized, but less obvious in terms of what they do. I.e. when you read the function definition, you don't go "oh, fibonacci".
Any pointers would be greatly appreciated!
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（3）
您需要对您的功能如何运作有一个心理模型。假设您自己执行函数，每次调用都使用纸片。第一个片段，您编写
(fib 250000)，然后您会看到“哦，我需要计算(fib 249999)和(fib 249998)最后添加它们”，因此您注意到这一点并开始两个新的剪贴簿留言。你不能扔掉第一个，因为当你完成其他计算时，它仍然有事情要做。你可以想象，这个计算将需要大量的废料。另一种方法不是从顶部开始，而是从底部开始。您将如何手动完成此操作？您可以从第一个数字 1、1、2、3、5、8 … 开始，然后始终添加最后两个数字，直到完成
i次。您甚至可以在每一步中扔掉除最后两个数字之外的所有数字，这样您就可以重复使用大多数碎片。这也是一个相当明显的实现，但是是如何，而不是什么。当您只需写下一个定义，它就会自动转换为有效的计算时，它总是看起来很优雅，但编程就是这种转换。如果某些东西自动转换，那么这个特定问题已经得到解决（通常以更通用的方式）。
思考“我将如何在纸上一步一步地做到这一点”通常会带来良好的实施。
You need to have a mental model of how your function works. Let's say that you execute your function yourself, using scraps of paper for each invocation. First scrap, you write
(fib 250000), then you see "oh, I need to calculate(fib 249999)and(fib 249998)and finally add them", so you note that and start two new scraps. You can't throw away the first, because it still has things to do for you when you finish the other calculations. You can imagine that this calculation will need a lot of scraps.Another way is not to start at the top, but at the bottom. How would you do this by hand? You would start with the first numbers, 1, 1, 2, 3, 5, 8 …, and then always add the last two, until you have done it
itimes. You can even throw away all numbers except the last two at each step, so you can re-use most scraps.This is also a fairly obvious implementation, but of the how to, not of the what. It always seems quite elegant when you can simply write down a definition and it gets automatically transformed into an efficient calculation, but programming is that transformation. If something gets transformed automatically, then this particular problem has already been solved (often in a more general way).
Thinking "how would I do this step by step on paper" often leads to a good implementaion.
以“简单”方式实现的斐波那契生成器（如序列的定义）总是会炸毁您的堆栈。对 fib 的两次递归调用都不是尾递归，这样的定义无法优化。
不幸的是，如果您想编写一个适用于大数字的有效实现，您将不得不接受这样一个事实：数学符号不能像我们希望的那样干净地转换为代码。
例如，非递归实现可以在 clojure.contrib.lazy 中找到-seqs。可以在 Haskell wiki 上找到解决此问题的各种方法。有了函数式编程的基础知识，理解它应该不难。
A Fibonacci generator implemented in a "plain" way, as in the definition of the sequence, will always blow your stack up. Neither of two recursive calls to
fibare tail recursive, such definition cannot be optimised.Unfortunately, if you'd like to write an efficient implementation working for big numbers you'll have to accept the fact that mathematical notation doesn't translate to code as cleanly as we'd like it to.
For instance, a non-recursive implementation can be found in clojure.contrib.lazy-seqs. A whole range of various approaches to this problem can be found on Haskell wiki. It shouldn't be difficult to understand with knowledge of basics of functional programming.