Trampoline
Récursion sûre pour la pile
Trampoline est une leçon Scala for Backend Engineering & Functional Programming gratuite sur CoddyKit. Ceci est la leçon 4 sur 4. Tu peux lire la leçon complète ci-dessous gratuitement — puis la pratiquer en direct dans le navigateur avec un éditeur de code intégré et un tuteur IA 24/7. Elle fait partie du parcours d'apprentissage Scala for Backend Engineering & Functional Programming, et ta progression se synchronise sur le web et l'application CoddyKit. Le cours Scala for Backend Engineering & Functional Programming comprend 4 leçons au total.
La limite de @tailrec
@tailrec optimise uniquement une fonction qui s’appelle directement elle-même. Elle ne peut pas aider pour la récursion mutuelle (deux fonctions qui s’appellent mutuellement), qui continue de faire croître la pile. La transformation par trampoline résout ce problème.
Le problème de la récursion mutuelle
Considérez isEven et isOdd, définies l’une en fonction de l’autre. Pour un grand nombre, elles provoquent un dépassement de pile et aucune ne peut être annotée avec @tailrec.
object Main {
def isEven(n: Int): Boolean = if (n == 0) true else isOdd(n - 1)
def isOdd(n: Int): Boolean = if (n == 0) false else isEven(n - 1)
def main(args: Array[String]): Unit = {
println(isEven(10))
}
}Qu’est-ce qu’un trampoline ?
Un trampoline transforme les appels récursifs en données. Au lieu de s’appeler elle-même, une fonction renvoie une description de l’étape suivante. Une boucle d’exécution répète ces étapes tout en maintenant une pile plate.
TailRec dans la bibliothèque standard
Scala fournit scala.util.control.TailCalls avec le type TailRec. Utilisez done(x) pour un résultat final et tailcall(...) pour différer l’appel suivant.
import scala.util.control.TailCalls._
object Main {
def isEven(n: Int): TailRec[Boolean] =
if (n == 0) done(true) else tailcall(isOdd(n - 1))
def isOdd(n: Int): TailRec[Boolean] =
if (n == 0) done(false) else tailcall(isEven(n - 1))
def main(args: Array[String]): Unit = {
println(isEven(100000).result)
}
}done et tailcall
Les deux éléments fondamentaux :
done(value)encapsule une réponse finale.tailcall(expr)diffère un appel qui renvoie unTailRec.
L’appel de .result exécute la boucle du trampoline et produit la valeur.
Sûreté de la pile
Comme chaque tailcall rend le contrôle à la boucle d’exécution au lieu d’imbriquer un appel Java, la pile de la JVM ne grandit jamais avec la profondeur de la récursion. L’exemple ci-dessus gère 100 000 étapes sans dépassement.
Transformer une récursion sur soi-même en trampoline
Les trampolines fonctionnent également pour une récursion profonde ordinaire sur soi-même, lorsque l’utilisation d’un accumulateur n’est pas simple. Ici, un compte à rebours profond reste sûr pour la pile.
import scala.util.control.TailCalls._
object Main {
def countDown(n: Int): TailRec[Int] =
if (n == 0) done(0) else tailcall(countDown(n - 1))
def main(args: Array[String]): Unit = {
println(countDown(500000).result)
}
}Combiner les résultats avec flatMap
TailRec prend en charge map et flatMap, ce qui vous permet d’effectuer un travail après un appel différé tout en restant sûr pour la pile.
import scala.util.control.TailCalls._
object Main {
def sum(n: Int): TailRec[Int] =
if (n == 0) done(0)
else tailcall(sum(n - 1)).map(_ + n)
def main(args: Array[String]): Unit = {
println(sum(100000).result)
}
}Fonctionnement de la boucle d’exécution
Conceptuellement, .result exécute une boucle : prendre l’étape actuelle ; si elle est done, renvoyer sa valeur ; s’il s’agit d’un appel différé, évaluer un niveau et continuer. Tout cela avec un espace de pile constant.
Les trampolines dans les bibliothèques d’effets
Des bibliothèques comme Cats Effect et ZIO transforment en interne leurs chaînes de flatMap en trampolines. Vous pouvez ainsi construire des programmes d’effets profondément imbriqués sans dépassement de pile. Le trampoline est au fondement des effets fonctionnels sûrs pour la pile.
Quand utiliser un trampoline
Utilisez un trampoline lorsque :
- Vous avez une récursion mutuelle qui ne peut pas devenir une seule fonction récursive terminale.
- La récursion est trop profonde pour la pile et qu’un accumulateur ne convient pas.
Pour une récursion simple sur soi-même, préférez d’abord @tailrec avec un accumulateur.
Vérification rapide
Vérifiez votre compréhension de la transformation par trampoline.
Récapitulatif
Vous avez appris la transformation par trampoline :
- Elle rend la récursion mutuelle et très profonde sûre pour la pile.
- Utilisez
TailCalls:done(x)ettailcall(...), puis.result. TailRecprend en chargemap/flatMap.- Elle constitue le fondement des bibliothèques d’effets sûres pour la pile.
Questions Fréquemment Posées
La leçon « Trampoline » est-elle gratuite ?
Oui — le texte complet de « Trampoline » est gratuit à lire ici sur le web. Pour la pratiquer de manière interactive (un éditeur de code intégré et un tuteur IA 24/7) et déverrouiller le reste du cours Scala for Backend Engineering & Functional Programming, passe à CoddyKit PRO. Le cours Scala for Backend Engineering & Functional Programming comprend 4 leçons au total.
Qu'est-ce que j'apprendrai dans « Trampoline » ?
Récursion sûre pour la pile Tu pratiques Scala for Backend Engineering & Functional Programming avec du code pratique que tu exécutes directement dans le navigateur, et un tuteur IA 24/7 répond à tes questions au fur et à mesure que tu avances dans la leçon.
Dois-je avoir de l'expérience pour commencer Scala for Backend Engineering & Functional Programming ?
Aucune expérience préalable n'est requise. Scala for Backend Engineering & Functional Programming sur CoddyKit est structuré pour les débutants jusqu'aux apprenants avancés, donc tu peux commencer ici ou depuis le début et avancer à ton rythme. Ceci est la leçon 4 sur 4.
Combien de temps prend la leçon « Trampoline » ?
La plupart des leçons CoddyKit prennent environ 5–10 minutes. Chacune est courte et interactive, tu progresses régulièrement et tu repiques exactement où tu t'es arrêté sur le web et l'app.
Peux-tu écrire et exécuter du code dans cette leçon Scala for Backend Engineering & Functional Programming ?
Oui. Chaque leçon Scala for Backend Engineering & Functional Programming inclut un éditeur de code intégré, tu écris et exécutes du vrai code directement dans ton navigateur et tu reçois des retours IA instantanés — aucune configuration locale requise.