Récursivité terminale / tail-recursivity

Récursivité terminale / tail-recursivity

[David.Bulone]

Bonjour,

    Y'a-t-il dans la littérature des résultats sur la transformation  
automatique de définitions récursives non terminales, en définitions  
de fonctions récursives terminales avec pile de taille bornée ?
    Sachant que le problème général est certainement indécidable,  
y'a-t-il des classes de fonctions pour lesquelles on sait faire cette  
tranformation ?
(par exemple, cette transformation est possible avec fibonacci et une  
pile de taille 2).
    Je travaille actuellement sur ce thème dans le cadre d'un TER.

Merci pour vos réponses.

----------------------------------------------------------------------------------
Hello,

    Is there in the literature some results about the automatic  
transformation of non tail-recursive functions definitions, into  
tail-recursive ones using a bounding stack ?
    The general problem is probably undecidable. But maybe there is  
some family of functions for which we know how to transform.
(for example, the transformation is possible for fibonacci sequence  
and a stack of size 2).
    I'm currently Master student (TER) working on that.

Thanks for yours responses.