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.

Monophony

In what sense is parsing not clean? – Devonne

There are many specificities that divert the attention from the mutual recursion itself. – Monophony

Also how easy is "easily reduced"? You can always take a bunch of mutually recursive functions and merge them into one function with a huge if-else-if-block. I'd consider that easy (albeit ugly and a bad idea maintainability-wise). However if we count that as easy, there simply is no example of mutually recursive functions that can't easily be reduced to a single recursive function. – Devonne

I don't think it is always possible. If the mutually-recursive function also calls itself in some cases that could result in infinite inlining loop. – Monophony

@Tibor: every recursion can be rewritten as a loop with an explicit stack. In fact, that's what compilers do. – Lebar

Assume your three mutually recursive functions are called f, g, h. Define an enum Fun with the values F, G, and H. Define a function fgh whose parameters are type of type Fun followed by a union of f's, g's and h's parameters and whose body has the form if(type == F) { fs body} else if (type==G) { gs body} etc.. Replace each occurrence of f in the body with fgh(F, arg1, arg2, null, null), each occurrence of g with fgh(G, null, null, arg, null) and each occurrence of h with fgh(H, null, null, null, arg). Done. – Devonne

Yes, I understand that. I meant without the explicit stack, just by inlining. – Monophony

You may have a look at this question #2725538 – Baptist

@Duc: If you read my question, you would see that I already did. – Monophony

Answer 1

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

Gorges

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.

Taishataisho

This is true, but I think this will almost never be cleaner/more logical than the actual use of two functions. – Monophony

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.

Foss

Not only does this example have code duplication (for M and C), it is also bad at generalizability -- increasing number of subjects would require making further copies of the same code. – Canticle

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.

Coniology