We’ve seen how recursion can be implemented efficiently (that is, without stack overflow), and also how the loop special form can be used to simulate a loop in an imperative language. These techniques work well if we’re dealing with simple recursion, in which a single function calls itself.
A more complex case is mutual recursion, in which two or more functions call each other recursively. Since recur always directs a function to call itself, it can’t be used in mutual recursion, so we can’t use it to avoid stack overflow. Most simple examples of mutual recursion are somewhat contrived, and the one about to be given is no exception, but it should serve to get the point across.
Suppose we are given a number and want to alternate between taking the square root and dividing by 2 until the result is less than 1. We can set up one function for taking the square root and another for dividing by 2, and use mutual recursion to perform the desired task:
(declare div2-recur)
(defn sqrt-recur [n]
(do
(println "sqrt-recur:" n)
(if (< n 1)
n
(div2-recur (Math/sqrt n)))))
(defn div2-recur [n]
(do
(println "div2-recur:" n)
(if (< n 1)
n
(sqrt-recur (/ n 2)))))
On line 1, we explicitly declare the second function div2-recur since it is referred to in the first function, and the Clojure reader will complain about an undefined symbol unless we declare it.
The sqrt-recur function takes a number n as an argument, prints it out, then tests if it is less than 1. If so, n is returned and the function ends. If not, a recursive call is made to div2-recur, passing the square root of n as the argument.
div2-recur works the same way, except it passes n/2 back to sqrt-recur. We can test the functions at the REPL:
=> (sqrt-recur 5)
sqrt-recur: 5
div2-recur: 2.23606797749979
sqrt-recur: 1.118033988749895
div2-recur: 1.057371263440564
sqrt-recur: 0.528685631720282
0.528685631720282
The number in the last line is just the final value of n returned from the last call to div2-recur.
However, because we’re not optimizing the recursive calls, if we give this program a large enough number, it will cause a stack overflow. The solution to this problem is not to use recur, as we did with single recursion, but rather a function called trampoline. To do this, we need to make a slight modification to each function. The revised functions are:
(declare div2-recur2)
(defn sqrt-recur2 [n]
(do
(println "sqrt-recur2:" n)
(if (< n 1)
n
#(div2-recur2 (Math/sqrt n)))))
(defn div2-recur2 [n]
(do
(println "div2-recur2:" n)
(if (< n 1)
n
#(sqrt-recur2 (/ n 2)))))
Apart from changing the names of the functions, the only change we made is the addition of a # in the last line of each function. This converts what was a function call in the first version to an anonymous function definition in the revised version. That is, instead of a recursive call being made to div2-recur2 from sqrt-recur2, an anonymous function is returned from sqrt-recur2. As it stands, there is no recursive call between the two functions any more. You can verify this by calling either function directly at the REPL:
=> (sqrt-recur2 5)
sqrt-recur2: 5
#<FunctionTest$sqrt_recur2__1356$fn__1358 .FunctionTest$sqrt_recur2__1356$fn__1358@5506d>
The first println in sqrt-recur2 prints out its value, and then we get a cryptic line of output which is Clojure’s internal representation of the anonymous function in the last line of sqrt-recur2.
However, if we use the built-in Clojure function trampoline, the functionality is magically restored:
=> (trampoline sqrt-recur2 5)
sqrt-recur2: 5
div2-recur2: 2.23606797749979
sqrt-recur2: 1.118033988749895
div2-recur2: 1.057371263440564
sqrt-recur2: 0.528685631720282
0.528685631720282
So what exactly is trampoline doing? We can find out by looking at its code (available in the clojure.core sourcecode listings):
(defn trampoline
([f]
(let [ret (f)]
(if (fn? ret)
(recur ret)
ret)))
([f & args]
(trampoline #(apply f args))))
The function can take either a single argument, or multiple arguments. Since we invoked it with 3 arguments, we’ll look at that bit (lines 7 and 8) first. trampoline assumes its first argument is a function (sqrt-recur2 in our example above), and it constructs an anonymous function which it then passes back to itself, thus causing the version of trampoline with a single argument to be called.
The anonymous function uses apply to apply the function f to the remaining arguments. In our example, the only remaining argument is 5, so sqrt-recur2 is applied to 5. However, look at what trampoline does with the function it is passed. The argument is tested to see if it is a function and, if so, recur gets the function ret to run, and passes whatever it returns as a recursive argument back into trampoline. In our example, calling sqrt-recur2 with an argument of 5 will return an anonymous function calling div2-recur2 with an argument that is the square root of 5. Thus trampoline receives another function as its argument in the recur, so it will call that function and pass its return value back into trampoline. Eventually, one of these function calls will return just a number (when that number is less than 1). At that point, the argument to trampoline will not be a function (rather, it’s just a number), so the recursion in trampoline stops, and the number itself is returned.
What has happened is that trampoline handles the mutual recursion by converting it into single recursion within the trampoline function, so that recur can be used to optimize the recursion and prevent a stack overflow. This is yet another example of the power of using first-class functions (functions that can be passed around as arguments to other functions).
One final note. Forcing the user to call this program by explicitly typing out a call to trampoline isn’t very friendly, so it’s a good idea to provide a wrapper that hides what’s going on. That’s easy enough to do by defining an auxiliary function:
(defn sqrt-div2 [n] (trampoline sqrt-recur2 n))
Now we can run the code by typing just (sqrt-div2 5).
Programming pages 