Re: [Caml-list] Récursivité terminale

[Xavier Leroy <Xavier.Leroy@inria.fr>]

>   Je voudrais savoir s'il existait un moyen de transformer une fonction 
> récursive non terminale en fonction récursive terminale avec Caml.

[ Translation: is there a way to transform a non-tail-recursive function
   into a tail-recursive function? ]

A technique that always works is to convert your function to
continuation-passing style.  The resulting code is hard to read and
not particularly efficient, though.

It is possible to do better in a number of specific cases.  Functions
operating over lists can often be made tail-rec by adding an
"accumulator" parameter and reversing the accumulator at the end.
For instance, List.map f l (not tail-rec) can be rewritten as
List.rev (List.rev_map f l) (tail-rec).

For more complex data structures than lists, Huet's zippers can often
be used for the same purpose.

Happy Googling,

- Xavier Leroy