Mutual recursion

Recursion need not be as “simple” and “direct” as having a function that calls itself. We can have more complex situations as a set of functions, each of which calls one or more of the others but not necessarily calling itself. (However, note that this is also allowed.)

Thinking in terms of mutual recursion is harder. For simple recursion, you had to imagine you already had a function to do something, and then you used it (in itself!) to do that. In mutual recursion, you have to think of a set of functions, each of which does its own part by simultaneously depending on all the set of functions: the others, and possibly itself as well.

Let’s examine a simple case to get our feet wet, and then go for a “real-life” application.

Odds and evens

How can you determine whether a (not negative) integer number is odd or even? This a trivial problem, to be sure (but see Question 9.11) but we can get an interesting solution...