Intent

To use mutually recursive functions to express certain algorithms, such as walking tree-like data structures, recursive descent parsing, and state machine manipulations

Overview

In Pattern 12, ​Tail Recursion​, we looked at using tail recursion to walk over sequences of data and the tricks that Clojure and Scala use to avoid consuming stack frames while doing so, since the JVM doesn’t directly support tail recursion.

For the majority of cases, the simple tail recursion we looked at in Pattern 12, ​Tail Recursion​, where the only recursive calls are self-recursive, is all we need. However, some of the more complex problems require solutions where functions can call each other recursively.

For instance, finite state machines are a great way of modeling many classes of problems, and mutual recursion is a great way to program them. Network protocols, many physical systems like vending machines and elevators, and parsing semistructured text can all be done with state machines.

In this pattern, we’ll look at some problems that can be solved cleanly using mutual recursion. Since the JVM doesn’t support tail recursive optimization, Scala and Clojure have to use a neat trick to support practical mutual recursion, just as they did with normal tail recursion, to avoid running out of stack space.

For mutual recursion, this trick is called a trampoline. Instead of making mutually recursive calls directly, we return a function that would make the desired call, and we let the compiler or runtime take care of the rest.

Scala’s support for trampolining hides a lot of the details of this and provides us with both a tailcall method to make mutually recursive calls and a done method to call when we’re done with the recursion.

That might sound bizarre, but it’s deceptively simple. To prove it, let’s take a quick look at the “Hello, World” for mutual recursion, a mathematically pretty but horribly inefficient way of telling if a number is even or odd, before we get into more real-world examples.

Here’s how it works: we need two functions, isEven and isOdd. Each function takes a single Long n. The isEven function checks to see if n is zero and, if so, it returns true. Otherwise it decrements n and calls isOdd. The isOdd method checks to see if n is zero and if so returns false. Otherwise it decrements n and calls isEven.

This is clearest in code, so here it is:

That works fine for small numbers, but what if we try it with a larger one?

As we can see, each mutually recursive call consumes a stack frame, so this causes our stack to overflow! Let’s see how to fix that using Scala’s trampoline.

Support for trampolining in Scala lives in scala.util.control.TailCalls, and it comes in two parts. The first is a done function, which is used to return the final result from the recursive calls. The second is a tailcall function, which is used to make the recursive calls.

In addition, the results returned by the tail recursive functions are wrapped in a TailRec type rather than being returned directly. To get them out at the end, we can call result on the final TailRec instance.

Here’s our even/odd code, rewritten to take advantage of Scala’s trampolining:

Let’s try running it:

This time, there’s no stack overflow with big numbers, though if you try with a big enough number, you should expect to wait a very long time, since this algorithm’s runtime is linearly proportional to the size of the number!

Also Known As

Indirect Recursion

Example Code: Phases of Matter

In this example, we’ll use Mutual Recursion to build a simple state machine that takes a sequence of transitions between the different phases of matter—liquid, solid, vapor, and plasma—and verifies that the sequence is valid. For instance, it’s possible to go from solid to liquid, but not from solid to plasma.

Each state in the machine is represented by a function, and the transitions are represented by a sequence of transition names, like condensation and vaporization. A state function picks the first transition off of the sequence and, if it’s valid, calls the function that gets it to where it should transition, passing it the remainder of the transitions. If the transition isn’t valid, we stop and return false.

For example, if we’re in the solid state and the transition we see is melting, then we call the liquid function. If it’s condensation, which isn’t a valid transition out of the solid state, then we immediately return false.

Before we jump into the code, let’s take a look at a picture of the phases-of-matter state machine.

---

Figure 12. The Phases of Matter. The phases of matter and the transitions between them

The nodes in this graph represent the functions we’ll need to model this state machine using Mutual Recursion, and the edges represent the transitions that those functions will operate on. Let’s take a look at the code, starting with Scala.

In Scala

Our Scala solution relies on four functions, one for each phase of matter: plasma, vapor, liquid, and solid. In addition, we’ll need a set of case objects to represent the transitions: Ionization, Deinonizaton, Vaporization, and so forth.

Each of the four functions takes a single argument and a List of transitions, and each uses Scala’s pattern matching to destructure it. If the list is Nil, then we know we’ve reached the end successfully and we call done, passing in true.

Otherwise, we check the first transition in the list to see if it’s valid. If so, we transition to the state it indicates and pass the remainder of the transitions. If the first transition isn’t valid, we call done, passing in false.

Let’s look at the code, starting with the case objects to represent our transitions. They’re pretty straightforward; each transition is its own object, and they all inherit from a Transition class.

Now let’s take a look at the meat of the example, the functions that represent our phases of matter. As promised, there are four: plasma, vapor, liquid, and solid. Here’s the full set of functions we’ll need:

We’ve already described how they work at a high level, so let’s pick apart one of them, vapor, in detail, starting with its signature:

As we can see, it just takes in a List of Transitions named transitions and takes pattern matches on it. Instead of returning a Boolean directly, it returns a TailRec of Boolean, so we can take advantage of Scala’s support for trampolining.

Moving on to the first case clause in the match expression, we see that it calls done to return true if the list is empty, or Nil. This is the base case of the recursion; if we get here it means we’ve successfully processed all the transitions originally in the sequence.

Next up are the three middle clauses. These use pattern matching to pick off the head of the sequence if it’s a valid transition and call the function to transition to the appropriate state, passing the rest of the transitions:

Finally, the last clause, which is a catchall. If we fall through to here, we know we haven’t processed all the transitions and the transition we saw wasn’t valid, so we call done and pass in false.

Let’s take a look at it in action, first with a valid list starting from the solid state:

Next we have an invalid list starting from the liquid state:

This wraps up our first look at Mutual Recursion in Scala. Let’s see how it looks in Clojure.

In Clojure

The Clojure code is similar to the Scala code, at least at a high level. We’ve got plasma, vapor, liquid, and solid functions, each of which takes a sequence of transitions.

We use Clojure’s destructuring to pick apart the sequence into the current transition, which we bind to transition and to the rest of the transitions in rest-transitions.

If transition is nil, we know we’ve reached the end successfully and we return true. Otherwise we check to see if it’s a valid transition, and, if so, we transition to the appropriate phase. If not, we return false. Here’s the full code:

Notice how there are no calls to done or tailcall like there are in the Scala version? Instead of using tailcall, we just return a function that will make the call we want to make. In this case, we’re using Clojure’s shorthand for anonymous functions to do so.

When we actually want to start the chain of mutually recursive calls, we pass the function we want to call into trampoline, along with its arguments:

This returns true for the valid sequence and false for the invalid one, just as we’d expect.

Before we leave this example, I’d like to talk a little bit about Nil in Scala and nil in Clojure. The code we wrote looked fairly similar, but there’s a subtle difference between the two nils that’s worth mentioning.

In Scala, Nil is just a synonym for the empty list, as we can see if we enter it into the Scala REPL:

In Clojure, nil just means “nothing”: it means that we don’t have a value, and it’s distinct from the empty list. Various functional languages have treated nil differently over the years, so whenever you come across a new one it’s always worth taking a minute to understand just what the language means by nil.

Discussion

Mutual Recursion can be pretty handy, but usually only in specific circumstances. State machines are one of these circumstances; they’re actually very useful little beasts. Unfortunately, most developers just remember them from their undergraduate computer science years, where they had to prove the equivalence between finite state machines and regular expressions, which is interesting but of no use to most developers.

State machines have been a bit more popular in recent years, though. They’re a big part of the actor model, a model for concurrent and distributed programming, that’s used by Scala’s Akka library and by Erlang, another functional language. Ruby has a clever gem for creating them, aptly named state_machine.

Another thing that’s worth noting is that the trampoline we saw here, in both Scala and Clojure, is just one way of doing Mutual Recursion. It’s only necessary because the JVM doesn’t implement tail call optimization directly.

Related Patterns

Pattern 5, ​Replacing Iterator​

Pattern 14, ​Filter-Map-Reduce​