Recursive Functions using a Trampoline in Clojure

Following on from yesterdays 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 back to a single call stack-frame being used, as opposed to the O(n) memory complexity faced at this time.

(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 core ‘trampoline’ function there is not a lot of boilerplate that is required to make this algorithm more efficient.

Factorial

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

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