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

labels » discussion

Mutual recurssion