clojure - 如何在 Clojure 中定义通用递归函数

Question

我对 Clojure 中的递归关系有一个通用函数的想法:

(defn recurrence [f inits]
  (let [answer (lazy-seq (recurrence f inits))
        windows (partition (count inits) 1 answer)]
    (concat inits (lazy-seq (map f windows)))))

然后，例如，我们可以将斐波那契数列定义为

(def fibs (recurrence (partial apply +) [0 1N]))

这对于少数人来说足够有效:

(take 10 fibs)
;(0 1N 1N 2N 3N 5N 8N 13N 21N 34N)

但是如果要求实现长序列，它会破坏堆栈:

(first (drop 10000 fibs))
;StackOverflowError ...

有什么办法可以克服这个问题吗？

Answer 1

这里的问题是，您在每次迭代中都会构建对 concat 的调用，并且 concat 调用会构建一大堆未评估的重击，当您最后求一个值。通过使用 cons 并且仅向前传递所需的值计数(和 concat，但不是递归堆栈吹 concat)，我们得到了一个表现更好的惰性序列:

user> 
(defn recurrence
  [f seed]
  (let [step (apply f seed)
        new-state (concat (rest seed) (list step))]
    (lazy-seq (cons step (recurrence f new-state)))))
#'user/recurrence
user> (def fibs (recurrence +' [0 1]))
#'user/fibs
user> (take 10 fibs)
(1 2 3 5 8 13 21 34 55 89)
user> (first (drop 1000 fibs))
113796925398360272257523782552224175572745930353730513145086634176691092536145985470146129334641866902783673042322088625863396052888690096969577173696370562180400527049497109023054114771394568040040412172632376N