如何正确使用尾递归？ [英] How to use tail recursion correctly?

问题描述

我正在尝试从 https重写这段代码：//github.com/lspector/gp/blob/master/src/gp/evolvefn_zip.clj

要使用递归：

I am trying to rewrite this piece of code from https://github.com/lspector/gp/blob/master/src/gp/evolvefn_zip.clj
to use recur:

(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)))))))

问题是，我绝对不知道该怎么做。

我唯一能想到的就是这样：

The problem is, I have absolutely no idea how to do that.
The only thing I can think of is something like this:

(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中的正常递归转换为尾递归？

It's not a working piece of code, it's just to show the way I would try to solve it, it would only get more and more convoluted.
Is there a better way to convert normal recursion to tail recursion in clojure?

推荐答案

这里有两个示例比较了递归算法和 loop-recur ：

Here are 2 examples comparing a recursive algorithm and 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-重复，您需要第二个循环变量（此处称为结果）来累积算法的输出。对于普通递归，调用堆栈会累积中间结果。

The basic difference is that for loop-recur you need a 2nd loop "variable" (here named result) to accumulate the output of the algorithm. For plain recursion, the call stack accumulates the intermediate result.

这篇关于如何正确使用尾递归？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！