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

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