What is the simplest example of mutual recursion?

Learning
1

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!

2

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
3

I’m curious, while this works

this doesn’t:

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

Line 3, characters 11-20:
3 |     | x -> odd (x-1)
               ^^^^^^^^^
Error: This expression has type 'a -> 'b
       but an expression was expected of type bool

Since function should pattern match on n, why doesn’t this work?

4

It’s because function ... returns a new function which immediately pattern matches on a single parameter. But in the second code sample you’ve already passed in the n parameter to both even and odd. So they end up effectively having two parameters each–n and the second pattern matched parameter. (Well, strictly speaking, due to currying, they are functions which take a single parameter and then return another function.)

Anyway, the type error is saying that odd (x-1) just applied one parameter and returned a function that expects the second parameter. You can get rid of this error by eliminating the n parameter from both functions.

5

@yawaramin oh, I thought function takes the last supplied parameter, n in my case. Coming from standard-ml, yet to get the hang of ocaml syntax. Thanks for the explanation.