recursion - 在 Clojure 中，是否可以将 memoization 和尾调用优化结合起来？

Question

在 clojure 中，我想写一个尾递归函数来内存它的 中级 的结果后续来电。

[编辑:这个问题已使用 gcd 重写。作为示例而不是 factorial .]

内存的gcd (最大公约数)可以这样实现:

(def gcd (memoize (fn [a b] 
   (if (zero? b) 
       a 
       (recur b (mod a b)))) 

在这个实现中， 中级 的结果不会被内存后续来电。例如，为了计算 gcd(9,6) , gcd(6,3)被称为中间结果。但是， gcd(6,3)由于 recur的递归点，没有存储在memoized函数的缓存中是未内存的匿名函数。

因此，如果在调用 gcd(9,6) 之后，我们调用 gcd(6,3)我们不会从内存中受益。

我能想到的唯一解决方案是使用普通递归(显式调用 gcd 而不是 recur )但是我们将不会从尾调用优化中受益。

底线

有没有办法同时实现:

尾调用优化

为后续调用记住中间结果

评论

这个问题类似于 Combine memoization and tail-recursion .但是那里的所有答案都与F#有关.在这里，我在 clojure 中寻找答案.

The Joy of Clojure 将这个问题留给读者作为练习。 (第 12.4 章)。您可以在http://bit.ly/HkQrio查阅本书的相关页面.

Answer 1

在您的情况下，很难显示 memoize 对阶乘做任何事情，因为中间调用是唯一的，所以我将重写一个有点做作的示例，假设重点是探索避免破坏堆栈的方法:

(defn stack-popper [n i] 
    (if (< i n) (* i (stack-popper n (inc i))) 1)) 

然后可以从内存中得到一些东西:

(def stack-popper 
   (memoize (fn [n i] (if (< i n) (* i (stack-popper n (inc i))) 1))))

不炸毁堆栈的一般方法是:

使用尾调用

(def stack-popper 
    (memoize (fn [n acc] (if (> n 1) (recur (dec n) (* acc (dec n))) acc))))

使用 trampolines

(def stack-popper 
    (memoize (fn [n acc] 
        (if (> n 1) #(stack-popper (dec n) (* acc (dec n))) acc))))
(trampoline (stack-popper 4 1))

使用惰性序列

(reduce * (range 1 4))

这些都不是一直有效的，尽管我还没有遇到过没有一个有效的案例。我几乎总是先选择懒惰的，因为我发现它们最像 clojure，然后我使用 recur 或 tramplines 进行尾部调用