Recursive Functions using a Trampoline in Clojure
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.
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.
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.
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.
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.
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.