## Mutual recurssion

"It's hard to know exactly how useful this is in practice, since I've never had cause to write mutually recursive functions, nor have I been able to think of a non-trivial example. However it's there."

It's not there just because it's fancy. If you need a non-trivial exemple, here is one.

1. We have the long multiplication product which is faster for small integers (say less than 1000 digits) but slower for bigger integers.

let long_mult_big (a: big_int) (b: big_int) =
let i = ref 0
and j = ref (Array.length b-1) in
let result = shift_big (scale_up_big a b.(!i)) !j
in begin
while !j > 0 do
incr i; decr j;
let _ = add_big result (shift_big (scale_up_big a b.(!i)) !j)
in ();
done;
result
end;;

2. We have the Karatsuba product wich is faster than "long_mult_big" for integers bigger than say 1000 digits.

3. We want "mult_big", a general product that offers best performance regardless integer size, we implement it using mutual recursion:

let karatsuba_threshold = 1000;;

let rec mult_big (a: big_int) (b: big_int) =
if Array.length a < Array.length b then
mult_big b a
else if Array.length b < karatsuba_threshold then
long_mult_big a b
else
karatsuba_mult_big a b
and karatsuba_mult_big (p: big_int) (q: big_int) =
assert (Array.length p >= Array.length q);
let len_p = Array.length p in
let len_q = Array.length q in
let n = len_p / 2 in
let a = Array.sub p 0 (len_p - n) in
let b = normalize p n in
if len_q > n then
let c = Array.sub q 0 (len_q - n) in
let d = normalize q n in
let ac = mult_big a c in
let bd = mult_big b d in
let ad_bc = sub_big (sub_big (mult_big (add_big a b) (sum_big c d)) ac) bd
in
add_big (add_big (shift_big ac (2*n)) (shift_big ad_bc n)) bd
else
let aq = mult_big a q in
let bq = mult_big b q in
add_big (shift_big aq n) bq;;

4. Of course the exemple is a bit too much advanced for a tutorial but one can't say mutual recursion is a luxury.

5. As a more general rule, even if during long experience you never have used a language feature, doesn't mean this feature is language-bloating. BrickCaster

-- I wrote that when I was relatively inexperienced in the language. Since then I have written quite a few mutually recursive functions. Richard W.M. Jones

-- I just browsed all my OCaml sources to see if there is a realistic mutual recursion exemple that can well fit in a tutorial, admittedly i can't find one. If i remember correctly, drawing the Dragon curve requires mutual recursion and is a nice beginner exemple. BrickCaster