Recursive Functions using a Trampoline in Clojure

Following on from yesterday’s post that discussed ‘Trampolining’ in JavaScript, I thought it would be interesting to see what Clojure has to offer.

Odd and Even

Using a mutually recursive algorithm such as the odd/even value checker below shows that we are still faced with stack-overflow issues when supplying a sufficiently sized input.

(declare is-even?)

(defn is-odd? [n]
  (if (zero? n)
    false
    (is-even? (dec n))))

(defn is-even? [n]
  (if (zero? n)
    true
    (is-odd? (dec n))))

(is-odd? 10000)
; Caused by: java.lang.StackOverflowError: null

However, with a little function wrapper addition and the use of the trampoline, we are able to return to a single call stack frame being used. This is in contrast to the O(n) memory complexity otherwise encountered.

(declare is-even?)

(defn is-odd? [n]
  (if (zero? n)
    false
    #(is-even? (dec n))))

(defn is-even? [n]
  (if (zero? n)
    true
    #(is-odd? (dec n))))

(trampoline (is-odd? 10000))

Thanks to the anonymous function shorthand macro and the core trampoline function, there is not a lot of boilerplate required to make this algorithm more efficient.

Factorial

We can also take advantage of the trampoline when faced with self-recursive tail-position calls. This is useful in an environment which does not implicitly optimise for such cases.

(defn factorial
  ([n] (factorial n 1))
  ([n acc] (if (< n 2) acc (factorial (dec n) (*' n acc)))))

(factorial 10000)
; Caused by: java.lang.StackOverflowError: null

It should be noted that with such a large input value, you may face an integer overflow exception before any stack overflow occurs. To accommodate this, the use of a BigInt (using the *' function) has been incorporated.

(defn factorial
  ([n] #(factorial n 1))
  ([n acc] (if (< n 2) acc #(factorial (dec n) (*' n acc)))))

(trampoline (factorial 10000))

Clojure does not provide implicit tail-call optimisation like other languages hosted on the JVM (Scala). However, you are able to assist the compiler in explicitly specifying such a need with the use of the recur function. The implementation below is very similar to the original, differing only in its use of ‘recur’ over the explicit function name in the tail-call positioned recursive call.

(defn factorial
  ([n] (factorial n 1))
  ([n acc] (if (< n 2) acc (recur (dec n) (*' n acc)))))