# labels/discussion

## 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 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