在Clojure中,我想编写一个尾递归函数,可以记忆其中间结果以供后续调用。
[编辑:本问题已使用gcd
作为示例重写,而不是factorial
。]
可将记忆化的gcd
(最大公约数)实现如下:
(def gcd (memoize (fn [a b]
(if (zero? b)
a
(recur b (mod a b))))
在这个实现中,中间结果不会被记忆化以供subsequent
调用使用。例如,为了计算gcd(9,6)
,会调用gcd(6,3)
作为中间结果。但是gcd(6,3)
没有被存储在记忆化函数的缓存中,因为recur
的递归点是未被记忆化的匿名函数。
因此,如果在调用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上查看相关页面。