Here’s a silly example to illustrate the difference between a tail recursive function and one that’s not. TCO won’t be performed on either, since Clojure quite reasonably doesn’t perform TCO. I want to illustrate the concept, though, and Clojure is familiar here. If we translated the code into another language TCO might be performed.
(defn oh-no-1 [] (println "Oh, no! We found a zero!!") nil)
;; not tail-recursive
(defn classify-until-zero-1
[xs]
(let [x (first xs)]
(cond (empty? xs) nil
(pos? x) (cons :p (classify-until-zero-1 (rest xs)))
(neg? x) (cons :n (classify-until-zero-1 (rest xs)))
(zero? x) (oh-no-1))))
(defn oh-no-2 [results] (println "Oh, no! We found a zero!!") results)
;; tail-recursive
(defn classify-until-zero-2
[acc xs]
(let [x (first xs)]
(cond (empty? xs) nil
(pos? x) (classify-until-zero-2 (conj acc :p) (rest xs))
(neg? x) (classify-until-zero-2 (conj acc :n) (rest xs))
(zero? x) (oh-no-2 acc))))
Here they are in action:
user=> (classify-until-zero-1 [1 -1 2 -2 0 3 -3])
Oh, no! We found a zero!!
(:p :n :p :n)
user=> (classify-until-zero-2 [] [1 -1 2 -2 0 3 -3])
Oh, no! We found a zero!!
[:p :n :p :n]
The tail recursive calls are in classify-until-zero-2
, in the lines beginning with (pos?
and (neg?
. Notice that nothing has to happen after the recursive calls return, even though they are not at the end of the function definition. (classify-until-zero-2
has an extra argument, acc
, for accumulator. You can avoid this by wrapping the function in another function, for example.)
By contrast, in classify-until-zero-1
, a cons
has to be performed after the recursive call returns. That’s why it’s not tail recursive: there is a function waiting to act. Those waiting function calls will build up on the stack. When TCO is possible, as in classify-until-zero-2
, the stack can be manipulated by the compiler so that that doesn’t happen.
I included two recursive calls in each function to show that tail recursion doesn’t necessarily have to do with a single recursive call. I included the oh-no
functions to show that there can be other branches that call other functions, without necessarily breaking tail recursion. (I didn’t illustrate mutual tail-recursion.)