在Clojure中,是否可以结合memoization和尾部调用优化？

Question

在clojure中,我想编写一个尾递归函数,为后续调用记忆其中间结果.

[编辑:这个问题已被重写gcd,而不是使用factorial.]

记忆gcd(最大公约数)可以像这样实现:

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

在此实现中,不会为后续调用记忆中间结果.例如,为了计算,称为中间结果.但是,没有存储在memoized函数的缓存中,因为递归点是未被记忆的匿名函数.gcd(9,6)gcd(6,3)gcd(6,3)recur

因此,如果在打电话后gcd(9,6),我们打电话说gcd(6,3)我们不会从备忘录中受益.

我能想到的唯一解决方案是使用普通的递归(明确地调用gcd而不是recur),但是我们不会从尾部调用优化中受益.

底线

有没有办法实现两者:

1. 尾调用优化
2. 为后续调用记录中间结果

备注

1. 这个问题类似于Combine memoization和tail-recursion.但那里的所有答案都与之相关F#.在这里,我正在寻找答案clojure.
2. 这个问题已经被"欢乐的Clojure"(第12.4章)留给了读者.您可以在http://bit.ly/HkQrio查阅该书的相关页面.

Answer 1

在你的情况下,很难显示memoize使用factorial做任何事情,因为中间调用是唯一的,所以我将重写一个有点人为的例子,假设关键是要探索避免堆栈的方法:

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

然后可以从memoize中获取一些东西:

(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))))

使用蹦床

(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,然后我前往尾巴调用复发或者繁殖