Example demonstrating good use of mutual recursion (original) (raw)

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.