在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
的递归点是未回传的匿名函数。
因此,如果在调用gcd(9,6)
之后,我们称之为gcd(6,3)
,那么我们将无法从回忆录中获益。
我能想到的唯一解决方案是使用普通的递归(可以明确地调用gcd
而不是recur
),但是这样我们就不会从尾调用优化中获益。
底线
是否有办法做到这两点:
备注
F#
有关。在这里,我正在寻找一个clojure
的答案。发布于 2012-03-28 06:45:30
(defmacro memofn
[name args & body]
`(let [cache# (atom {})]
(fn ~name [& args#]
(let [update-cache!# (fn update-cache!# [state# args#]
(if-not (contains? state# args#)
(assoc state# args#
(delay
(let [~args args#]
~@body)))
state#))]
(let [state# (swap! cache# update-cache!# args#)]
(-> state# (get args#) deref))))))
这将允许递归定义回传函数,该函数还缓存中间结果。用法:
(def fib (memofn fib [n]
(case n
1 1
0 1
(+ (fib (dec n)) (fib (- n 2))))))
发布于 2012-03-30 10:16:45
(def gcd
(let [cache (atom {})]
(fn [a b]
@(or (@cache [a b])
(let [p (promise)]
(deliver p
(loop [a a b b]
(if-let [p2 (@cache [a b])]
@p2
(do
(swap! cache assoc [a b] p)
(if (zero? b)
a
(recur b (mod a b))))))))))))
有一些并发问题(双重评估,与回忆录相同的问题,但更糟糕的是,因为承诺),这些问题可以用@kotarak的建议来解决。
将上述代码转换为宏是留给读者的练习。(福格斯的笔记是国际海事组织开玩笑的。)
将其转化为宏实际上是一项简单的宏操作,请注意身体(最后三行)保持不变。
发布于 2012-03-27 21:54:24
使用Clojure的重述,您可以使用没有堆栈增长的累加器编写阶乘,只需回溯:
(defn fact
([n]
(fact n 1))
([n acc]
(if (= 1 n)
acc
(recur (dec n)
(* n acc)))))
https://stackoverflow.com/questions/9898069
复制相似问题