The most important basic example of a datatype that can be defined by mutual recursion is a tree, which can be defined mutually recursively in terms of a forest (a list of trees).
This definition is elegant and easy to work with abstractly (such as when proving theorems about properties of trees), as it expresses a tree in simple terms: a list of one type, and a pair of two types.
This definition is more compact, but somewhat messier: a tree consists of a pair of one type and a list of another, which require disentangling to prove results about.
Common examples include algorithms on trees, and recursive descent parsers.
A standard example of mutual recursion, which is admittedly artificial, determines whether a non-negative number is even or odd by defining two separate functions that call each other, decrementing by 1 each time.
This example is mutual single recursion, and could easily be replaced by iteration.
A similar approach to multitasking is to instead use coroutines which call each other, where rather than terminating by calling another routine, one coroutine yields to another but does not terminate, and then resumes execution when it is yielded back to.
This allows individual coroutines to hold state, without it needing to be passed by parameters or stored in shared variables.
There are also some algorithms which naturally have two phases, such as minimax (min and max), which can be implemented by having each phase in a separate function with mutual recursion, though they can also be combined into a single function with direct recursion.
This can sometimes be done more elegantly via mutually recursive functions; the Sierpiński curve is a good example.
For example, Abelson and Sussman describe how a meta-circular evaluator can be used to implement LISP with an eval-apply cycle.
Some programming styles discourage mutual recursion, claiming that it can be confusing to distinguish the conditions which will return an answer from the conditions that would allow the code to run forever without producing an answer.
[9] If there is only one site where one procedure calls the other, this is straightforward, though if there are several it can involve code duplication.