Recursion Revisited

Clojure works very hard to balance the power of functional programming with the reality of the Java Virtual Machine. One example of this is the well-motivated choice of explicit TCO through loop/recur.

But blending the best of two worlds always runs the risk of unpleasant compromises, and it makes sense to ask the question, “Does Clojure contain hidden design compromises that, while not obvious on day one, will bite me later?”

This question is never fully answerable for any language, but let’s consider it by exploring some more complex recursions. First, we’ll look at mutual recursion.

A mutual recursion occurs when the recursion bounces between two or more functions. Instead of A calls A calls A, we have A calls B calls A again. As a simple example, you could define my-odd? and my-even? using mutual recursion:

Because my-odd? and my-even? each call the other, you need to create both vars before you define the functions. You could do this with def, but the declare macro lets you create both vars (with no initial binding) in a single line of code.

Verify that my-odd? and my-even? work for small values:

my-odd? and my-even? consume stack frames proportional to the size of their argument, so they will fail with large numbers.

This is similar to the problem that motivated the introduction of recur. But you can’t use recur to fix it, because recur works with self-recursion, not mutual recursion. Of course, odd/even can be implemented more efficiently without recursion anyway. Clojure’s implementation uses bit-and (bitwise and) to implement odd? and even?:

We picked odd/even for its simplicity. Other recursive problems are not so simple and don’t have an elegant nonrecursive solution. We’ll examine four approaches you can use to solve such problems:

• Converting to self-recursion
• Trampolining a mutual recursion
• Replacing recursion with laziness
• Shortcutting recursion with memoization

Converting to Self-recursion

Mutual recursion is often a nice way to model separate but related concepts. For example, oddness and evenness are separate concepts but clearly related to one another.

You can convert a mutual recursion to a self-recursion by coming up with a single abstraction that deals with multiple concepts simultaneously. For example, you can think of oddness and evenness in terms of a single concept: parity. Define a parity function that uses recur and returns 0 for even numbers and 1 for odd numbers:

Test that parity works for small values:

At this point, you can trivially implement my-odd? and my-even? in terms of parity:

Parity is a straightforward concept. Unfortunately, many mutual recursions will not simplify into an elegant self-recursion. If you try to convert a mutual recursion into a self-recursion and you find the resulting code to be full of conditional expressions that obfuscate the definition, then don’t use this approach.

Trampolining Mutual Recursion

A trampoline is a technique for optimizing mutual recursion. A trampoline is like an after-the-fact recur, imposed by the caller of a function instead of the implementer. Since the caller can call more than one function inside a trampoline, trampolines can optimize mutual recursion.

Clojure’s trampoline function invokes one of your mutually recursive functions:

If the return value is not a function, then a trampoline works just like calling the function directly. Try trampolining a few simple Clojure functions:

If the return value is a function, then trampoline assumes you want to call it recursively and calls it for you. trampoline manages its own recur, so it will keep calling your function until it stops returning functions.

Back in ​Tail Recursion​, you implemented a tail-fibo function. You saw how the function consumed stack space and replaced the tail recursion with a recur. Now we have another option. You can take the code of tail-fibo and prepare it for trampolining by wrapping the recursive return case inside a function.

The only difference between this and the original version of tail-fibo is the initial # on line 7. Try bouncing trampoline-fibo on a trampoline:

Since trampoline does a recur, it can handle large inputs just fine, without throwing a StackOverflowError:

We’ve ported tail-fibo to use trampoline to compare and contrast trampoline and recur. For self-recursions like trampoline-fibo, trampoline offers no advantage, and you should prefer recur. But with mutual recursion, trampoline comes into its own.

Consider the mutually recursive definition of my-odd? and my-even?, which we presented at the beginning of ​Recursion Revisited​. You can convert these broken, stack-consuming implementations to use trampoline, with the same approach you used to convert tail-fibo: prepend a # to any recursive tail calls so that they return a function to produce the value, rather than the value itself:

The only difference from the original implementation is the function wrappers on lines 6 and 11. With this change in place, you can trampoline large values of n without blowing the stack:

A trampoline is a special-purpose solution to a specific problem. It requires doctoring your original functions to return a different type to indicate recursion. If one of the other techniques presented here provides a more elegant implementation for a particular recursion, that’s great. If not, you’ll be happy to have trampoline in your box of tools. In practice, many Clojure programmers never encounter a case requiring trampoline at all.

Replacing Recursion with Laziness

Of all the techniques for eliminating or optimizing recursion discussed in this chapter, laziness is the one you’ll probably use most often.

For our example, we’ll implement the replace function developed by Eugene Wallingford to demonstrate mutual recursion. (See http://www.cs.uni.edu/~wallingf/patterns/recursion.html.)

replace works with an s-list data structure, which is a list that can contain both symbols and lists of symbols. replace takes an s-list, an oldsym, and a newsym and replaces all occurrences of oldsym with newsym. For example, this call to replace replaces all occurrences of b with a:

The following is a fairly literal translation of the Scheme implementation from Wallingford’s paper. We’ve converted from Scheme functions to Clojure functions, changed the name to replace-symbol to avoid collision with Clojure’s replace, and shortened names to better fit the printed page, but otherwise, we’ve preserved the structure of the original:

The two functions replace-symbol and replace-symbol-expression are mutually recursive, so a deeply nested structure could blow the stack. To demonstrate the problem, create a deeply-nested function that builds deeply nested lists containing a single bottom element:

Try deeply-nested for a few small values of n:

Clojure provides a *print-level* that controls how deeply the Clojure printer will go into a nested data structure. Set the *print-level* to a modest value so that the printer doesn’t go crazy trying to print a deeply nested structure. You’ll see that when we nest deeper, the printer simply prints a # and stops:

Now, try to use replace-symbol to change bottom to deepest for different levels of nesting. You’ll see that large levels blow the stack. Depending on your JVM implementation, you may need a larger value than the 10000 shown here:

All of the recursive calls to replace-symbol are inside a cons. To break the recursion, all you have to do is wrap the recursion with lazy-seq. It’s really that simple. You can break a sequence-generating recursion by wrapping it with a lazy-seq. Here’s the improved version. Since the transition to laziness was so simple, we couldn’t resist the temptation to make the function more Clojure-ish in another way as well:

On line 4, the lazy-seq breaks the recursion, preventing stack overflow on deeply nested structures. The other improvement is on line 2. Rather than have two different functions to deal with symbols and lists, there’s a single multimethod replace-symbol with one method for lists and another for symbols. (Multimethods are covered in detail in Chapter 9, ​Multimethods​.) This gets rid of an if form and improves readability.

Make sure the improved replace-symbol can handle deep nesting:

Laziness is a powerful ally. You can often write recursive and even mutually recursive functions and then break the recursion with laziness.

Shortcutting Recursion with Memoization

To demonstrate a more complex mutual recursion, let’s look at the Hofstadter Female and Male sequences. The first Hofstadter sequences were described in Gödel, Escher, Bach: An Eternal Golden Braid [Hof99]. The Female and Male sequences are defined as follows:^[26]

F(0) = 1; M(0) = 0

F(n) = n - M(F(n-1)), n > 0

M(n) = n - F(M(n-1)), n > 0

This suggests a straightforward definition in Clojure:

The Clojure definition is easy to read and closely parallels the mathematical definition. However, it performs terribly for large values of n. Each value in the sequence requires calculating two other values from scratch, which in turn requires calculating two other values from scratch. On one of our MacBook Pro computers,^[27] it takes more than half a minute to calculate (m 250):

Is it possible to preserve the clean, mutually recursive definition and have decent performance? Yes, with a little help from memoization. Memoization trades space for time by caching the results of past calculations. When you call a memoized function, it first checks your input against a map of previous inputs and their outputs. If it finds the input in the map, it can return the output immediately, without having to perform the calculation again.

Rebind m and f to memoized versions of themselves, using Clojure’s memoize function:

Now Clojure needs to calculate F and M only once for each n. The speedup is enormous. Calculating (m 250) is thousands of times faster:

And, of course, once the memoization cache is built, “calculation” of a cached value is almost instantaneous:

Memoization alone is not enough, however. Memoization shortcuts the recursion only if the memoization cache is already populated. If you start with an empty cache and ask for m or f of a large number, you’ll blow the stack before the cache can be built:

The final trick is to guarantee that the cache is built from the ground up by exposing sequences, instead of functions. Create m-seq and f-seq by mapping m and f over the whole numbers:

Now callers can get M(n) or F(n) by taking the nth value from a sequence:

The approach is quite fast, even for larger values of n:

The approach we used here is as follows:

• Define a mutually recursive function in a natural way.

• Use memoization to shortcut recursion for values that have already been calculated.

• Expose a sequence so that dependent values are cached before they’re needed.

This approach is heap consuming, in that it caches all previously seen values. If this is a problem, in some situations, you can eliminate it by selecting a more complex caching policy.

We’ve spent much of this chapter exploring different techniques for implementing and leveraging laziness. However, Clojure also provides a range of solutions for eager evaluation of transformations over collections. Next, we’ll explore when these are preferred and how to perform eager transformations.