Table des matières
Problème de récursion ?
Tremplin
sum ?
Utilisez des types pour décrire les tremplins
Appel de Fibonacci
Maison Java javaDidacticiel Trampoline, exemple en Java

Trampoline, exemple en Java

Jan 17, 2025 pm 08:18 PM

Trampolim, exemplo em Java

Écrivons un programme simple pour additionner des nombres de n à 0. Mais au lieu d’utiliser une approche itérative, pourquoi ne pas essayer une approche récursive ?

Nous appelons ce programme sum. Nous savons sum(0) == 0, c'est donc notre cas de base. Comment arrive-t-on au cas de base ? sum(n) == n sum(n-1), jusqu'à finalement atteindre sum(0). Le code Java est le suivant :

int sum(int n) {
    if (n == 0) {
        return 0;
    }
    return n + sum(n - 1);
}
Copier après la connexion
Copier après la connexion

Problème de récursion ?

La récursion a un défaut inhérent lorsque le cas de base est éloigné de la valeur d'entrée... Dans la plupart des langages, les appels de fonction utilisent la pile du programme pour stocker les informations sur les appels de fonction, donc de très grandes récursions peuvent provoquer un débordement de pile.

Mais existe-t-il un moyen d’éviter cela ? En fait, il y en a. Il s’agit d’une vieille stratégie appelée trampoline.

Tremplin

L'idée de base de la stratégie tremplin est qu'une partie du programme renvoie une « valeur » ou une « suite ». Qu'est-ce que la suite ? Une fonction qui continuera le traitement.

C'est à peu près comme suit :

let trampolim = primeiraChamada(input);

while (trampolim is continuation) {
    trampolim = trampolim.continue();
}
return trampolim;
Copier après la connexion
Copier après la connexion
Copier après la connexion
Copier après la connexion
Quelle est la suite de

sum ?

Modélisons sum le programme comme : Au lieu de simplement récursif, utilisez des continuations. Une solution consiste à utiliser acc comme objet passé via une continuation. Alors quand sum_trampoline(0, acc) est atteint, on revient acc. Comment procéder ?

Passons de sum_trampoline(n, acc) à sum_trampoline(n-1, acc n). La première entrée est sum_trampoline(n, 0).

Donc, le code est le suivant :

Object sum_trampoline_bootstrap(int n) {
    return sum_trampoline(n, 0);
}

Object sum_trampoline(int n, int acc) {
    if (n == 0) {
        return acc;
    }
    return (Supplier<object>) () -> sum(n - 1, acc + n);
}
Copier après la connexion
Copier après la connexion

Utilisez des types pour décrire les tremplins

Le tremplin doit être grossièrement de la forme suivante :

let trampolim = primeiraChamada(input);

while (trampolim is continuation) {
    trampolim = trampolim.continue();
}
return trampolim;
Copier après la connexion
Copier après la connexion
Copier après la connexion
Copier après la connexion

Mais cela donne beaucoup de liberté de codage et n'est pas très intuitif pour le monde Java. On peut vérifier s'il s'agit d'une continuation en interrogeant l'objet. Et si nous demandions « La valeur a-t-elle été trouvée ? » Une autre chose est que puisque Java n'a pas de types somme, return trampolim renverra en fait le type trampolim au lieu de renvoyer la valeur. Nous pouvons retourner à trampolim.value().

Enfin, un point clé est le bootstrapping du tremplin. Pour ce faire, nous pouvons utiliser une fonction pour convertir l'entrée en la valeur de retour pogo appropriée. Les entrées et les résultats peuvent être généralisés pour une meilleure utilisation :

public static <R> R trampoline(IN input,
                                   Function<IN, TrampolineStep<R>> trampolinebootStrap) {
  TrampolineStep<R> nextStep = trampolinebootStrap.apply(input);
  while (!nextStep.gotValue()) {
    nextStep = nextStep.runNextStep();
  }
  return nextStep.value();
}
Copier après la connexion
Copier après la connexion

TrampolineStep<R>Et l'interface ?

Il définit trois méthodes :

  • gotValue : Demande si la valeur a été trouvée
  • value : Renvoie la valeur trouvée
  • runNextStep : Renvoie une valeur ou une suite

Il a essentiellement deux états :

  • Valeur trouvée
  • C'est une continuation

Par conséquent, nous pouvons utiliser des méthodes statiques pour l'initialiser. Dans les cas où la valeur a été trouvée, la valeur doit être transmise :

int sum(int n) {
    if (n == 0) {
        return 0;
    }
    return n + sum(n - 1);
}
Copier après la connexion
Copier après la connexion

Pour le cas de suite, vous devez indiquer comment obtenir l'élément suivant de la suite :

let trampolim = primeiraChamada(input);

while (trampolim is continuation) {
    trampolim = trampolim.continue();
}
return trampolim;
Copier après la connexion
Copier après la connexion
Copier après la connexion
Copier après la connexion

sum_trampolineComment cela sera-t-il réalisé ?

Object sum_trampoline_bootstrap(int n) {
    return sum_trampoline(n, 0);
}

Object sum_trampoline(int n, int acc) {
    if (n == 0) {
        return acc;
    }
    return (Supplier<object>) () -> sum(n - 1, acc + n);
}
Copier après la connexion
Copier après la connexion

Appel de Fibonacci

L'implémentation classique de Fibonacci suit la définition récursive :

let trampolim = primeiraChamada(input);

while (trampolim is continuation) {
    trampolim = trampolim.continue();
}
return trampolim;
Copier après la connexion
Copier après la connexion
Copier après la connexion
Copier après la connexion

Il existe également une version itérative qui étend la définition de Fibonacci non pas de manière récursive, mais vers l'avant : en commençant par 0 et 1 jusqu'à ce que les valeurs correspondantes soient atteintes :

public static <R> R trampoline(IN input,
                                   Function<IN, TrampolineStep<R>> trampolinebootStrap) {
  TrampolineStep<R> nextStep = trampolinebootStrap.apply(input);
  while (!nextStep.gotValue()) {
    nextStep = nextStep.runNextStep();
  }
  return nextStep.value();
}
Copier après la connexion
Copier après la connexion

Il existe une version avancée de cette implémentation, utilisant la « récursivité des appels de queue » :

static <X> TrampolineStep<X> valueFound(X value) {
    return new TrampolineStep() {
        @Override
        public boolean gotValue() {
            return true;
        }

        @Override
        public X value() {
            return value;
        }

        @Override
        public TrampolineStep<X> runNextStep() {
            return this;
        }
    };
}
Copier après la connexion

Ici, je sépare l'interface de saisie, qui prépare les nombres qui seront utilisés dans l'appel récursif de Fibonacci. Au fur et à mesure qu'il avance, nous commençons par la cartographie fib[0] => 0, fib[1] => 1 et naviguons depuis l'index 0 jusqu'à atteindre l'index n.

Fibonacci : du tail call au tremplin

L'exemple de

fib_tc illustre bien le tremplin de Fibonacci :

static <X> TrampolineStep<X> goonStep(Supplier<TrampolineStep<X>> x) {
    return new TrampolineStep() {
        @Override
        public boolean gotValue() {
            return false;
        }

        @Override
        public X value() {
            throw new RuntimeException("dont call this");
        }

        @Override
        public TrampolineStep<X> runNextStep() {
            return x.get();
        }
    };
}
Copier après la connexion

Veuillez noter qu'il ne s'agit que d'un squelette et nécessite une implémentation complète de l'interface TrampolineStep et une implémentation complète des fonctions trampoline pour compiler et exécuter. De plus, IN doit être remplacé par un type d'entrée spécifique.

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!

Déclaration de ce site Web
Le contenu de cet article est volontairement contribué par les internautes et les droits d'auteur appartiennent à l'auteur original. Ce site n'assume aucune responsabilité légale correspondante. Si vous trouvez un contenu suspecté de plagiat ou de contrefaçon, veuillez contacter admin@php.cn

Outils d'IA chauds

Undresser.AI Undress

Undresser.AI Undress

Application basée sur l'IA pour créer des photos de nu réalistes

AI Clothes Remover

AI Clothes Remover

Outil d'IA en ligne pour supprimer les vêtements des photos.

Undress AI Tool

Undress AI Tool

Images de déshabillage gratuites

Clothoff.io

Clothoff.io

Dissolvant de vêtements AI

Video Face Swap

Video Face Swap

Échangez les visages dans n'importe quelle vidéo sans effort grâce à notre outil d'échange de visage AI entièrement gratuit !

Outils chauds

Bloc-notes++7.3.1

Bloc-notes++7.3.1

Éditeur de code facile à utiliser et gratuit

SublimeText3 version chinoise

SublimeText3 version chinoise

Version chinoise, très simple à utiliser

Envoyer Studio 13.0.1

Envoyer Studio 13.0.1

Puissant environnement de développement intégré PHP

Dreamweaver CS6

Dreamweaver CS6

Outils de développement Web visuel

SublimeText3 version Mac

SublimeText3 version Mac

Logiciel d'édition de code au niveau de Dieu (SublimeText3)

Sujets chauds

Tutoriel Java
1664
14
Tutoriel PHP
1267
29
Tutoriel C#
1239
24
Le logiciel de sécurité de l'entreprise entraîne-t-il l'exécution de l'application? Comment dépanner et le résoudre? Le logiciel de sécurité de l'entreprise entraîne-t-il l'exécution de l'application? Comment dépanner et le résoudre? Apr 19, 2025 pm 04:51 PM

Dépannage et solutions au logiciel de sécurité de l'entreprise qui fait que certaines applications ne fonctionnent pas correctement. De nombreuses entreprises déploieront des logiciels de sécurité afin d'assurer la sécurité des réseaux internes. ...

Comment convertir les noms en nombres pour implémenter le tri et maintenir la cohérence en groupes? Comment convertir les noms en nombres pour implémenter le tri et maintenir la cohérence en groupes? Apr 19, 2025 pm 11:30 PM

Solutions pour convertir les noms en nombres pour implémenter le tri dans de nombreux scénarios d'applications, les utilisateurs peuvent avoir besoin de trier en groupe, en particulier en un ...

Comment simplifier les problèmes de cartographie des champs dans l'amarrage du système à l'aide de mapstruct? Comment simplifier les problèmes de cartographie des champs dans l'amarrage du système à l'aide de mapstruct? Apr 19, 2025 pm 06:21 PM

Le traitement de la cartographie des champs dans l'amarrage du système rencontre souvent un problème difficile lors de l'exécution d'amarrage du système: comment cartographier efficacement les champs d'interface du système a ...

Comment Intellij Idea identifie-t-elle le numéro de port d'un projet de démarrage de printemps sans publier un journal? Comment Intellij Idea identifie-t-elle le numéro de port d'un projet de démarrage de printemps sans publier un journal? Apr 19, 2025 pm 11:45 PM

Commencez le printemps à l'aide de la version IntelliJideaultimate ...

Comment obtenir élégamment des noms de variables de classe d'entité pour créer des conditions de requête de base de données? Comment obtenir élégamment des noms de variables de classe d'entité pour créer des conditions de requête de base de données? Apr 19, 2025 pm 11:42 PM

Lorsque vous utilisez MyBatis-Plus ou d'autres cadres ORM pour les opérations de base de données, il est souvent nécessaire de construire des conditions de requête en fonction du nom d'attribut de la classe d'entité. Si vous manuellement à chaque fois ...

Comment convertir en toute sécurité les objets Java en tableaux? Comment convertir en toute sécurité les objets Java en tableaux? Apr 19, 2025 pm 11:33 PM

Conversion des objets et des tableaux Java: Discussion approfondie des risques et des méthodes correctes de la conversion de type de distribution De nombreux débutants Java rencontreront la conversion d'un objet en un tableau ...

Comment utiliser la solution Redis Cache pour réaliser efficacement les exigences de la liste de classement des produits? Comment utiliser la solution Redis Cache pour réaliser efficacement les exigences de la liste de classement des produits? Apr 19, 2025 pm 11:36 PM

Comment la solution de mise en cache Redis réalise-t-elle les exigences de la liste de classement des produits? Pendant le processus de développement, nous devons souvent faire face aux exigences des classements, comme l'affichage d'un ...

Plateforme de commerce électronique SKU et conception de la base de données SPU: comment prendre en compte à la fois les attributs définis par l'utilisateur et les produits sans attribution? Plateforme de commerce électronique SKU et conception de la base de données SPU: comment prendre en compte à la fois les attributs définis par l'utilisateur et les produits sans attribution? Apr 19, 2025 pm 11:27 PM

Explication détaillée de la conception des tables SKU et SPU sur les plates-formes de commerce électronique Cet article discutera des problèmes de conception de la base de données de SKU et SPU dans les plateformes de commerce électronique, en particulier comment gérer les ventes définies par l'utilisateur ...

See all articles