Récursion terminale

Récursion terminale

Lorsqu'un appel récursif est enveloppé par une opération associative on peut rajouter un paramètre pour obtenir un appel terminal.

let rec foo = function arg ->
  if (arg = arg_0)
  then val_0
  else op(foo(g(arg)), f(arg));;

où f et g ne contiennent pas foo, devient lorsque op est associative :

let rec foo = function (arg,accu)
  if (arg = arg_0)
  then op(accu,val_0)
  else foo(g(arg) , op(accu, f(arg)));;