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