Clojure 中的尾部调用优化

Question

我有以下功能。

   (defn get-all-str
      "Get a list of all strings of length n,
       consisting of characters from the alphabet list
       and not containing two identical characters in a row."
      [n alphabet]
      (letfn [(add-to-result [current-string result]
                (if (= (count current-string) n)
                  (conj result current-string)
                  (loop [remaining-alphabet (remove #(= % (last current-string)) alphabet)
                         acc result]
                    (if (empty? remaining-alphabet)
                      acc
                      (recur (rest remaining-alphabet)
                             (add-to-result (str current-string (first remaining-alphabet)) acc))))))]
        (if (<= n 0)
          []
          (add-to-result "" []))))

我正在使用recur，但我仍然没有进行尾递归，因为我以通常的方式调用

add-to-result

。如何重新排列这个函数以将其变成尾递归？

Answer 1

尾递归并不是 Clojure 中生成序列的默认工具。当然，有时这是适当的，但更多时候，懒惰是实用的。例如，在这里，非尾递归的危险在于您可能拥有比 JVM 支持的更多的堆栈帧。但只要您仅使用与输出字符串的长度成正比的堆栈帧，而不是与生成的输出字符串的number成正比，就应该没问题。即使是由 3 个符号组成的非常小的字母表，长度为 100 的字符串数量也大约是 2^100，这远远超出了您的处理能力。因此，只要你只使用 100 个堆栈帧来生成这个列表，你就会耗尽时间，而不是堆栈帧。

这是使用递归惰性序列编写此函数的一种简单方法。它的效率不是很高，但很简单。

(defn non-repeating-strings [length alphabet]
  (let [a (set alphabet)]
    (letfn [(step [n prev]
              (if (= n 1)
                [[prev]]
                (for [sym (disj a prev)
                      more (step (dec n) sym)]
                  (cons prev more))))]
      (for [sym a
            result (step length sym)]
        (apply str result)))))