28 août 2009

17 messages - Retourner à l'article

Voir tous les messages - Retourner à l'article

  • Elimination des fonctions auto-invocantes..

    le 19 novembre 2018 à 17:00

    Il y a un hic . Vous proposez, avec une fonction
    « racineCarreRecursion » auto-invocante :
    epsilon = 10 ** (-100000)
    semence = 2
    def racineCarreRecursion(x,y) :
    if (y**2 - x) < epsilon :
    return y
    else :
    return racineCarreRecursion(x,(x/y + y)/2.0)
    def racineCarre(x) :
    return racineCarreRecursion(x,semence)

    Quand on l’expérimente par exemple pour racine de 1000 et
    avec ce très petit epsilon : :
    raci = racineCarre(1000)
    print("raci=",raci)

    la réponse est immédiate et sans débordement de pile
    >>>
    raci= 2, ce qui est faux.

    Explication, il y avait une erreur d’étourderie dans le
    test d’arrêt du bouclage. Mutatis mutandis le programme corrigé est
    epsilon = 10 ** (-100000)
    semence = 2
    def racineCarreRecursion(x,y) :
    if abs(y**2 - x) < epsilon :
    return y
    else :
    return racineCarreRecursion(x,(x/y + y)/2.0)
    def racineCarre(x) :
    return racineCarreRecursion(x,semence)

    raci = racineCarre(1000)
    print(« raci= »,raci)

    résultat :
    RuntimeError : maximum recursion depth exceeded in comparison

    C’est naturel avec une fonction auto-invocante ; d’ailleurs même avec un
    epsilon moins sévère on déborde vite: :
    epsilon = 10 ** (-333)
    A l’opposé pour
    epsilon = 10 ** (-300) qui donnera
    raci= 31.622776601683793

    la réponse est bonne et très rapide car cet algorithme de
    racine converge très vite, en une dizaine de tours pour cet epsilon.

    Je maintiens bien que la récursion avec une fonction auto-invocante est
    à rejeter si on ne sait pas à l’avance combien de tours notre algorithme
    exigera, cette arcane de récursivité était facile à expérimenter et tous les contributeurs de sites comme stackoverflow ou rosettacode ou medium présentent ce défaut.

    Mais ce n’était pas ma question d’origine : trouver sur le web une
    implémentation « correcte » d’un combinateur de point fixe en python. Il
    faut se rendre à l’évidence, on n’en trouve pas à cette date.
    Par conséquent j’allège mes exigences de « correction » ; écrire un simulateur de
    Y-C (même comportement vu de l’extérieur) et surtout abondonner l’exigence de
    lui fournir un seul argument, mais accepter deux ou trois arguments qui
    expriment la récurrence souhaitée, ces arguments étant de préférence des
    « functions » lambdas. Dès que ce sera au point je publierai.

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