如何正确使用尾递归？

Question

我正在尝试重写 https://github.com/lspector/gp/blob/master/src/gp/evolvefn_zip.clj
中的这段代码使用循环：

(defn random-code [depth]
  (if (or (zero? depth)
          (zero? (rand-int 2)))
    (random-terminal)
    (let [f (random-function)]
      (cons f (repeatedly (get function-table f)
                          #(random-code (dec depth)))))))

问题是，我完全不知道该怎么做。
我唯一能想到的是这样的：

(defn random-code [depth]
  (loop [d depth t 0 c []]
    (if (or (zero? depth)
            (zero? (rand-int 2)))
      (if (= t 0)
        (conj c random-terminal)
        (recur depth (dec t) (conj c (random-terminal))))
      (let [f (random-function)]
        (if (= t 0)
          (recur (dec depth) (function-table f) (conj c f))
          (recur depth (dec t) (conj c f)))))))

这不是一段有效的代码，它只是为了展示我尝试解决它的方法，它只会变得越来越复杂。
有没有更好的方法将普通递归转换为 clojure 中的尾递归？

Answer 1

这里有 2 个比较递归算法和 loop-recur:

的例子

(defn fact-recursion [n]
  (if (zero? n)
    1
    (* n (fact-recursion (dec n)))))

(defn fact-recur [n]
  (loop [count  n
         result 1]
    (if (pos? count)
      (recur (dec count) (* result count))
      result )))

(fact-recursion 5) => 120
(fact-recur 5) => 120

(defn rangy-recursive [n]
  (if (pos? n)
    (cons n (rangy-recursive (dec n)))
    [n]))

(defn rangy-recur [n]
  (loop [result []
         count  n]
    (if (pos? count)
      (recur (conj result count) (dec count))
      result)))

(rangy-recursive 5) => (5 4 3 2 1 0)
(rangy-recur 5) => [5 4 3 2 1]

基本区别在于，对于 loop-recur，您需要第二个循环 "variable"（此处命名为 result）来累积算法的输出。对于普通递归，调用堆栈累积中间结果。

如何正确使用尾递归？

How to use tail recursion correctly?

recursion

clojure

tail-recursion