Un tremplin vers des fonctions au-delà des primitives récursives ? Implémentation pour la fonction Ackermann Peter

En explorant la technique du tremplin, je l'ai d'abord utilisée dans des situations plus simples, avec une seule récursion – probablement un sous-ensemble approprié de fonctions récursives primitives. Cependant, le besoin s'est fait sentir d'effectuer un calcul extrêmement long au travail. Ma première idée était la fonction busy beaver, mais, en plus de sa grande complexité informatique, je n'étais pas assez familière. J'ai alors opté pour une fonction plus connue : la fonction Ackermann-Peter.

La fonction Ackermann-Peter

Il s'agit d'une fonction facile à comprendre qui prend deux arguments entiers en entrée :

int ackermannPeter(int m, int n) {
    if (m == 0) {
        return n + 1;
    } else if (n == 0) {
        return ackermannPeter(m - 1, 1);
    }
    return ackermannPeter(m - 1, ackermannPeter(m, n - 1));
}

Pour plus de détails, consultez la page Wikipédia ou WolframAlpha.

Utilisation de la fonction

Lors du test ackermannPeter(3, 3), le résultat a été calculé correctement. Cependant, lors de l'exécution de ackermannPeter(4, 3), une explosion de pile s'est produite. La profondeur des appels récursifs à la fonction Ackermann-Peter est très grande ; en changeant simplement le premier argument de 3 à 4, le résultat, qui était 61, devenait $2^{2^{65536}} - 3$.

Surmonter la limite de pile

Le problème réside dans la récursion intense de la fonction Ackermann-Peter, qui épuise rapidement la pile. La solution est d'utiliser des continuations pour éviter de surcharger la pile, en mettant en œuvre l'idée du tremplin.

Un pas sur le trampoline nécessite trois comportements :

• Indiquez si le calcul est terminé.
• Renvoyer la valeur calculée.
• Exécutez une étape et obtenez la suite suivante.

Pour notre cas (retour entier) :

interface Continuation {
    boolean finished();
    int value();
    Continuation step();

    static Continuation found(int v) { /* ... */ }
    static Continuation goon(Supplier<Continuation> nextStep) { /* ... */ }
}

Le trampoline lui-même :

static int compute(Continuation c) {
    while (!c.finished()) {
        c = c.step();
    }
    return c.value();
}

Application à la fonction Ackermann-Peter : la fonction est divisée en trois cas : cas de base, récursivité simple et double récursivité. Le tremplin devrait contrôler le résultat de la deuxième récursion. Pour ce faire, le deuxième argument devient un Continuation. Si n est déjà terminé, le processus continue normalement ; sinon, une étape est franchie dans la suite, en générant une nouvelle.

private static Continuation ackermannPeter(int m, Continuation c) {
    if (!c.finished()) {
        return Continuation.goon(() -> {
            final var next = c.step();
            return Continuation.goon(() -> ackermannPeter(m, next));
        });
    }
    int n = c.value();
    if (m == 0) {
        return Continuation.found(n + 1);
    } else if (n == 0) {
        return Continuation.goon(() -> ackermannPeter(m - 1, Continuation.found(1)));
    }
    return Continuation.goon(() ->
        ackermannPeter(m - 1,
            Continuation.goon(() -> ackermannPeter(m, Continuation.found(n - 1)
        )))
    );
}

Ajout de mémorisation

La mémorisation améliore les performances. Deux situations : 1) le résultat est déjà en mémoire ; 2) l'étape suivante vous permet de déduire le résultat actuel. La mémorisation est appliquée après avoir résolu la suite du deuxième argument. L'implémentation avec mémorisation à l'aide d'une touche HashMap et long (combinant m et n) est présentée, démontrant une réduction significative du nombre d'appels récursifs. La version finale supprime la dépendance globale à la mémoire, en passant HashMap comme argument.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!