我是 Clojure 的新手,我认为到目前为止我编写代码的方法不符合“Clojure 之道”。至少,我一直在编写一些函数,这些函数不断导致值较大的 StackOverflow 错误。我已经了解了如何使用 recur,这是向前迈出的一大步。但是,如何使像下面这样的函数适用于 2500000 这样的值呢?
(defn fib [i]
(if (>= 2 i)
1
(+ (fib (dec i))
(fib (- i 2)))))
在我看来,该函数是斐波那契生成器的“简单”实现。我见过其他更优化的实现,但就其功能而言不太明显。 IE。当您阅读函数定义时,您不会说“哦,斐波那契”。
任何指点将不胜感激!
最佳答案
您需要对您的功能如何运作有一个心理模型。假设您自己执行函数,每次调用都使用纸片。第一个片段,您编写 (fib 250000)
,然后您会看到“哦,我需要计算 (fib 249999)
和 (fib 249998)
最后添加它们”,因此您注意到这一点并开始两个新的剪贴簿留言。你不能扔掉第一个,因为当你完成其他计算时它仍然有事情要做。你可以想象这个计算需要大量的碎片。
另一种方法不是从顶部开始,而是从底部开始。您将如何手动完成此操作?您可以从第一个数字 1、1、2、3、5、8 … 开始,然后始终添加最后两个数字,直到完成 i
次。您甚至可以在每一步中扔掉除最后两个数字之外的所有数字,这样您就可以重复使用大多数碎片。
(defn fib [i]
(loop [a 0
b 1
n 1]
(if (>= n i)
b
(recur b
(+ a b)
(inc n)))))
这也是一个相当明显的实现,但是如何,而不是什么。当您只需写下一个定义,它就会自动转换为有效的计算时,它总是看起来很优雅,但编程就是这种转换。如果某些东西自动转换,那么这个特定问题已经得到解决(通常以更通用的方式)。
思考“我如何在纸上一步一步地做到这一点”通常会带来良好的实现。
关于recursion - 我该如何编写这个 Clojure 函数才不会耗尽堆栈?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/8671376/