Example demonstrating good use of mutual recursion

Question

I would like to know if there is a non-artificial example, where mutual recursion is the most elegant solution to a problem and it cannot be easily reduced/inlined to a single recursive function.

I already know this example (from Wikipedia)

function even?(number : Integer)
    if number == 0 then
        return true
    else
        return odd?(abs(number)-1)

function odd?(number : Integer)
    if number == 0 then
        return false
   else
        return even?(abs(number)-1)

But seriously, no one in their right mind would check the number's parity this way.

I checked the previous answer on this topic here on SO - Are there any example of Mutual recursion? but none of the answers are what I am looking for.

I know it can be useful in recursive parsing - probably the only logical way to implement it, but I need a cleaner, more specific example (preferably a mathematical one).

Thank you for help?

Edit:

Since apparently every tuple of mutually-recursive functions CAN be reduced to a single functions, I would rather want to know if there is a case where use of mutually recursive functions is the best/most readable way.

Answer 1

Mutual recursive code for drawing of Sierpinski curve (and some other curves) looks rather elegant.

Answer 2

I believe any mutual recursion can easily be reduced into a single function:

consider two functions f1 and f2:

f1(p1, ..., pn) returns r1
f2(q1, ..., qm) returns r2

can be unified to:

f12(which, p1, ..., pn, q1, ..., qn) returns (r1, r2)
    if which == 1
        <code of f1>
    else
        <code of f2>

This is just the worst case. Usually some parameters or the return values should be the same.

Answer 3

It's up to one's individual sensitivities what one considers "elegant". But here's my shot.

Adam is trying to schedule a 6-day exam revision. On each day he's going to either:

1. Rest (R)
2. Study Maths (M)
3. Study Computing (C)

Adam never studies two different subjects on two consecutive days. In how many ways can Adam schedule his revision?

Solution:

Let's use the notation s1 = "RMCRMM" to represent a schedule. s1 is not a valid schedule, because at one point in the schedule a subject (M) is immediately followed by another subject (C). Some examples of valid schedules would be: s2 = "MMRCCR" or s3 = "MMRRRC" or even s4 = "RRRRRR" (good luck with s4!). In each schedule there has to be at least one rest day between two different subjects.

We can solve the task using mutual recursion. Let us enumerate days starting from 1, 2, ..., 6. Let us define three mutually recursive functions, R(k), M(k), C(k). Each function is going to compute the number of partial schedules, each of length k, where the last days are, respectively "R", "M" and "C". Here we go (python):

def R(k):
    if k == 1:
        return 1
    else:
        return R(k-1) + M(k-1) + C(k-1)

def M(k):
    if k == 1:
        return 1
    else:
        return R(k-1) + M(k-1)

def C(k):
    if k == 1:
        return 1
    else:
        return R(k-1) + C(k-1)

We can then solve the problem by evaluating R(6) + M(6) + C(6)

The reason this works is because we're counting possible ways to get to a (partial) schedule for k days, which can end in a given way, and the only thing, which can possibly influence our choice of how we get there is what happened on the day before. In such way we count all possible schedules and we count each schedule exactly once.

For example, for day 3, which we finished, say at "C", "XXC", the number of ways we could have got to such schedule is exactly R(2) + C(2), since we could have come from a schedule "XCC" or "XRC", but not "XMC".

Obviously, if you'd like to make this more efficient you'd probably end up using memoisation/ dynamic programming, but even then, mutual recursion would likely be the most readable/ understandable way to code up the problem.

Answer 4

If you have proper tail call optimization, you can do cooperative multitasking:

f():
    do_something()
    g()

g():
    do_something_else()
    f()

If you happen to code in Scheme, this is something to consider at times.