Tail call optimization in Clojure

Question

I have the following function.

   (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 "" []))))

I'm using recur, but I still haven't done tail recursion since I'm calling add-to-result in the usual way. How do I rearrange this function to turn it into a tail recursion?

UPD:

For some reason stack overflow is deleting my thank you comments. I'll try to post here. Thank you all very much for your replies! You all helped me a lot to understand

Answer 1

Tail recursion is not really the default tool for producing sequences in Clojure. It is appropriate sometimes, of course, but more often laziness is practical. For example, here, the danger of non-tail recursion is that you might have more stack frames than the JVM supports. But as long as you only use stack frames proportional to the length of the output strings, and not proportional to the number of output strings produced, you should be fine. Even with a very small alphabet of 3 symbols, the number of strings of length 100, say, is around 2^100, which well exceeds your ability to process. So as long as you only use 100 stack frames to produce this list, you will run out of time, not stack frames.

Here is one simple way to write this function with recursive lazy sequences. It is not terribly efficient, but it is straightforward. Importantly, it is also lazy, so you can get partial results when passing parameters that make the result list too large to fully process with tail recursion.

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

user=> (non-repeating-strings 3 "abc")
("aba" "abc" "aca" "acb" "bab" "bac" "bca" "bcb" "cab" "cac" "cba" "cbc")

Answer 2

When this algorithm is implemented using recursion, the partial result during computation is stored in the stack of the JVM. To express this algorithm without recursion using just a loop, that partial result needs to be stored elsewhere, for example in a loop variable that we call stack in the code example below:

(defn loop-get-all-str [n alphabet]
  (let [alphabet (set alphabet)]
    (loop [[s & stack] [""]
           result []]
      (if s
        (if (= n (count s))
          (recur stack (conj result s))
          (recur (into stack
                       (map (partial str s))
                       (disj alphabet (last s)))
                 result))
        result))))