Récursivité terminale

Récursivité terminale

[David.Bulone]

Bonjour,

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

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

[Xavier Leroy]

>   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

Re: Récursivité terminale

[Chung-chieh Shan]

(So that's how you say "tail-recursive" in French...)

Xavier Leroy <Xavier.Leroy@inria.fr> wrote in article <49CB9854.1020707@inria.fr> in gmane.comp.lang.caml.inria:
> 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).

In fact, it is always possible to do better in the sense above:
the accumulator parameter arises mechanically as the result of
defunctionalizing the continuation in a CPS program.  For example, if we
transform "List.map f l (not tail-rec)" into CPS then defunctionalize
it, we get essentially "List.rev (List.rev_map f l) (tail-rec)".

Sometimes we can improve upon the first-order representation of
continuations chosen mechanically by defunctionalization.  The factorial
function is an example: defunctionalization represents a continuation
by a list of numbers, but we can replace the list by the product of the
numbers.

-- 
Edit this signature at http://www.digitas.harvard.edu/cgi-bin/ken/sig
100 Days to close Guantanamo and end torture http://100dayscampaign.org/
http://www.avaaz.org/en/end_the_war_on_terror/