Should not a tail-recursive function also be faster?
- by Balint Erdi
I have the following Clojure code to calculate a number with a certain "factorable" property. (what exactly the code does is secondary).
(defn factor-9
([]
(let [digits (take 9 (iterate #(inc %) 1))
nums (map (fn [x] ,(Integer. (apply str x))) (permutations digits))]
(some (fn [x] (and (factor-9 x) x)) nums)))
([n]
(or
(= 1 (count (str n)))
(and (divisible-by-length n) (factor-9 (quot n 10))))))
Now, I'm into TCO and realize that Clojure can only provide tail-recursion if explicitly told so using the recur keyword. So I've rewritten the code to do that (replacing factor-9 with recur being the only difference):
(defn factor-9
([]
(let [digits (take 9 (iterate #(inc %) 1))
nums (map (fn [x] ,(Integer. (apply str x))) (permutations digits))]
(some (fn [x] (and (factor-9 x) x)) nums)))
([n]
(or
(= 1 (count (str n)))
(and (divisible-by-length n) (recur (quot n 10))))))
To my knowledge, TCO has a double benefit. The first one is that it does not use the stack as heavily as a non tail-recursive call and thus does not blow it on larger recursions. The second, I think is that consequently it's faster since it can be converted to a loop.
Now, I've made a very rough benchmark and have not seen any difference between the two implementations although. Am I wrong in my second assumption or does this have something to do with running on the JVM (which does not have automatic TCO) and recur using a trick to achieve it?
Thank you.
