The other day I stumbled across some Clojure code that used mutual recursion. Mutual recursion can be a valuable tool when solving a problem. Unfortunately because of the lack of tail call optimization on the JVM this can be a dangerous technique when writing Clojure code. It can be easy to forget about this limitation and end up writing code that blows the stack.
Take the classic even/odd checking code from the Wikipedia page. If we just translate it to Clojure it will cause a stack overflow error when we pass in a large number. The massive number of function calls require before returning causes too much memory to be consumed.
1 2 3 4 5 6 7 8 9 10 11 12 13 14
Luckily since Clojure 1.0 there has been a useful function for dealing with this.
trampoline, with minor modifications to your code, can be used to get around the lack of tail call optimizations (docs here).
trampoline takes a function (and, if needed, arguments to pass into the function) and calls it. If the function returns a function then
trampoline calls that. As long as functions are returned
trampoline will continue calling them. When a non-function value is returned
trampoline returns, passing through the value.
To make our sample code work with
trampoline we simply change our functions to return a closure which wraps the call that was previously being executed. This just entails putting a
# before the final s-exp. This takes advantage of Clojure’s anonymous function syntax to change the function call into a closure which is returned.
1 2 3 4 5 6 7 8 9
By doing this we’ve changed how the caller interacts with
my-odd?. It now needs to be called by
Now we no longer suffer from the stack overflow error.
I think we can still do better though, because now the caller of
my-odd? suffers since they are forced to remember to use
trampoline. By forcing this on the caller, we’ve pushed what should be hidden implementations details into the callers code. We can fix this by pushing the use of
trampoline into our functions.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
Now we have the best of both worlds. Mutual recursion without the worry of a stack overflow and functions that don’t force the caller to be aware of the implementation details.