Version française
Home     About     Download     Resources     Contact us    

This site is updated infrequently. For up-to-date information, please visit the new OCaml website at

Browse thread
Récursivité terminale
[ Home ] [ Index: by date | by threads ]
[ Search: ]

[ Message by date: previous | next ] [ Message in thread: previous | next ] [ Thread: previous | next ]
Date: 2009-03-26 (14:59)
From: Xavier Leroy <Xavier.Leroy@i...>
Subject: Re: [Caml-list] Récursivité_terminale
>   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, 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