如何正确使用尾递归？

我试图从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中的尾递归？

来源

2017-02-21 buggy3

是的，解决方案很可能像您的代码一样复杂。你正在建造一棵树的原因，而不是一个序列。如果你建立一个序列，你通常会添加一个累加器参数，它将替换代码中的连接符。在你的情况下，所有功能都是2个childreen的节点，它不起作用，你不能向两个孩子发送一个acc。为什么你想要尾递归？如果你想生成一个DEPTH大于Java堆栈的树，你只需要这个。 Java没有1000帧深栈的问题。尾递归可能会比你的版本慢。 – mattias

这里有两个例子比较递归算法和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你需要一个第二环“变量”（这里命名result）累积算法的输出。对于简单的递归，调用堆栈会累加中间结果。

来源

2017-02-22 00:24:58

如何正确使用尾递归？

回答

相关问题