recursion - 我该如何编写这个 Clojure 函数才不会耗尽堆栈？

Question

我是 Clojure 的新手，我认为到目前为止我编写代码的方法不符合“Clojure 之道”。至少，我一直在编写一些函数，这些函数不断导致值较大的 StackOverflow 错误。我已经了解了如何使用 recur，这是向前迈出的一大步。但是，如何使像下面这样的函数适用于 2500000 这样的值呢？

(defn fib [i]
  (if (>= 2 i)
    1
    (+ (fib (dec i))
       (fib (- i 2)))))

在我看来，该函数是斐波那契生成器的“简单”实现。我见过其他更优化的实现，但就其功能而言不太明显。 IE。当您阅读函数定义时，您不会说“哦，斐波那契”。

任何指点将不胜感激!

Answer 1

您需要对您的功能如何运作有一个心理模型。假设您自己执行函数，每次调用都使用纸片。第一个片段，您编写 (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)))))

这也是一个相当明显的实现，但是如何，而不是什么。当您只需写下一个定义，它就会自动转换为有效的计算时，它总是看起来很优雅，但编程就是这种转换。如果某些东西自动转换，那么这个特定问题已经得到解决(通常以更通用的方式)。

思考“我如何在纸上一步一步地做到这一点”通常会带来良好的实现。