28 août 2009

17 messages - Retourner à l'article

Voir tous les messages - Retourner à l'article

  • Élimination des fonctions « auto-invocantes »

    le 21 novembre 2018 à 17:30, par Pierre Lescanne

    Je pense que la page de discussion de cet article n’est pas le lieu pour un tel échange que je vous propose, si vous le souhaitez, continuer sur un autre médium (par exemple le courriel). Je voudrais pour les autres lecteurs rappeler les points suivants.

    1. Mon programme ne comporte pas d’étourderie.

    2. Il ne faut pas mélanger les concepts. Le fait que abs(y**2 - x) < epsilon soit une mauvaise condition d’arrêt d’une approximation relève de l’arithmétique des ordinateurs et n’a rien à voir avec la récursivité et l’itération, comme cela est montré par le comportement des deux programmes itératifs suivants. Je précise que je n’ai pas l’intention d’aborder le problème de l’arrêt des itérations et des meilleurs moyens d’approximer une quantité réelle. Il y a des ouvrages spécialisés sur le sujet et mon domaine d’expertise est le lambda-calcul et la récursivité.

    def rac2While(x) :
       y = semence
       while (y**2 - x) >= epsilon:
           y = (x/y + y)/2.0
       return y

    et

    def rac2WhileAbs(x) :
       y = semence
       while abs(y**2 - x) >= epsilon:
           y = (x/y + y)/2.0
       return y

    Le calcul de rac2While(2) converge et la calcul de rac2WhileAbs(2) diverge.

    3. Je ne connais pas le concept de « fonction auto-invocante ». Peut-être voulez-vous parler de fonction récursive ? J’affirme clairement et sans ambage, qu’avec les fonctions récursives on peut programmer un algorithme pour lequel on ne connaît pas à l’avance le nombre d’appels récursifs imbriqués qui seront nécessaires. C’est ce qui distingue les fonctions récursives (générales) des fonctions récursives primitives. Python implante les fonctions récursives (générales). Ce sont ces fonctions récursives que j’utilise régulièrement quand je programme dans des langages de programmation où la seule structure de contrôle est la récursivité.

    4. Quant à l’implantation d’un combinateur de point fixe en python, je pense y avoir suffisamment répondu. Vous y arriverez très probablement (car python est Turing-complet). Vous pourrez même le faire sans aucune boucle « while », en utilisant uniquement la récursivité ! Mais je doute que cela soit élégant et naturel. Je ne suis donc pas étonné que vous n’ayez pas trouvé de références pertinentes sur le web.

    Bien cordialement, et à bientôt sur un autre médium, si vous le souhaitez.

    Pierre Lescanne

    Répondre à ce message
Pour participer à la discussion merci de vous identifier : Si vous n'avez pas d'identifiant, vous pouvez vous inscrire.