 # What is the simplest example of mutual recursion?

I wanted to see an example that was the simplest for mutual recursion. I saw this:

``````(*
https://ocaml.org/learn/tutorials/labels.html#Mutually-recursive-functions
*)

let rec even n =
match n with
| 0 -> true
| x -> odd (x-1)
and odd n =
match n with
| 0 -> false
| x -> even (x-1);;
``````

which is correct but personally I end u having to reason to much about the example and why its correct. If the initial call is of a certain parity (say u call odd) then u insert an even number then it ends up with the same call as the initial parity function and depending on that it will be true or false. e.g. if odd n_odd then the final number will end with even 0 so it returns true as desired. Similarly if odd n_even then it ends with odd 0 and returns false. If it does even n_odd then it ends with odd 0 which is false and even n_even ends with even 0 which is true. Just to much reasoning going around and the example is NOT evident to me why its correct.

If anyone can provide a simpler example (less contrived) that would be great!

There seems to be a lot of “reasoning” because you are unfolding the recursive calls in your mind.
A simpler way to look at it is to rephrase it like this:
The first function tells if a number n is even by using this rule: if n is 0, then n is indeed even. Otherwise, it is even if (n-1) is odd.
The second function tells if a number is odd by comparing it to 0: if it is 0, then it is not odd. Otherwise, it is odd if n-1 is even.

I think this is quite understandable, and also literally what the program is doing.
Then of course, you also have to convince yourself that these mutually recursive functions do terminate, and that is easy to check that they will for any n>=0.
Frankly, I doubt you could come by an example much simpler than this one.

2 Likes