Schémas d’accumulation
Faites circuler l’état dans la récursion.
Schémas d’accumulation est une leçon Scala for Backend Engineering & Functional Programming gratuite sur CoddyKit. Ceci est la leçon 2 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.
Pourquoi utiliser des accumulateurs
La récursivité simple construit son résultat lors de la remontée de la pile d'appels, après le retour de l'appel récursif.
Un accumulateur transporte au contraire un résultat intermédiaire dans chaque appel, de sorte que la réponse soit prête lorsque le cas de base est atteint.
Ce petit changement permet la récursivité terminale et une utilisation constante de la pile.
La fonction auxiliaire
Le modèle de l'accumulateur utilise une fonction auxiliaire interne qui reçoit un paramètre supplémentaire : le résultat obtenu jusque-là.
La fonction externe se contente de la lancer avec une valeur initiale, souvent 0 ou une liste vide.
def sum(xs: List[Int]): Int = {
def loop(rest: List[Int], acc: Int): Int = rest match {
case Nil => acc
case h :: t => loop(t, acc + h)
}
loop(xs, 0)
}Exécuter l'accumulateur
Voici le programme complet qui additionne une liste à l'aide d'un accumulateur.
Remarquez que le cas de base renvoie directement acc, et non 0. Le total a été construit au fur et à mesure de la descente dans la liste.
def sum(xs: List[Int]): Int = {
def loop(rest: List[Int], acc: Int): Int = rest match {
case Nil => acc
case h :: t => loop(t, acc + h)
}
loop(xs, 0)
}
@main def run(): Unit =
println(sum(List(1, 2, 3, 4))) // 10Comparer les deux formes
Dans la récursivité simple, l'étape de combinaison (h + ...) attend l'appel interne.
Dans la version avec accumulateur, la combinaison a lieu avant l'appel, et l'appel est la toute dernière action de la fonction.
C'est cette propriété du dernier appel qui rend la fonction récursive terminale.
// Plain: combine after the call
case h :: t => h + sum(t)
// Accumulator: combine before the call
case h :: t => loop(t, acc + h)Récursivité terminale
Un appel récursif terminal est un appel où l'appel récursif constitue la dernière action de la fonction, sans rien à effectuer ensuite.
Scala peut l'optimiser en boucle en réutilisant un seul cadre de pile, de sorte qu'il ne déborde jamais, quelle que soit la profondeur.
import scala.annotation.tailrec
@tailrec
def countDown(n: Int): Unit =
if (n < 0) ()
else { println(n); countDown(n - 1) }L'annotation @tailrec
Ajouter @tailrec demande au compilateur de vérifier que la fonction est bien récursive terminale.
Si ce n'est pas le cas, la compilation échoue avec une erreur claire. Cela transforme un piège de performance silencieux en garantie à la construction.
import scala.annotation.tailrec
def sum(xs: List[Int]): Int = {
@tailrec
def loop(rest: List[Int], acc: Int): Int = rest match {
case Nil => acc
case h :: t => loop(t, acc + h)
}
loop(xs, 0)
}
@main def run(): Unit = println(sum((1 to 100000).toList))Accumuler une liste
Les accumulateurs ne sont pas obligés de contenir des nombres. Ils peuvent aussi construire des collections.
Cette fonction reverse ajoute chaque tête au début de l'accumulateur, ce qui inverse naturellement l'ordre. L'ajout au début avec :: est rapide ; cette approche est donc efficace.
def reverse[A](xs: List[A]): List[A] = {
def loop(rest: List[A], acc: List[A]): List[A] = rest match {
case Nil => acc
case h :: t => loop(t, h :: acc)
}
loop(xs, Nil)
}Reverse en action
L'accumulateur commence vide et grandit à mesure que nous consommons l'entrée.
Comme chaque tête est placée au début de acc, le premier élément se retrouve à la fin, ce qui produit une liste inversée avec un coût de pile constant.
def reverse[A](xs: List[A]): List[A] = {
def loop(rest: List[A], acc: List[A]): List[A] = rest match {
case Nil => acc
case h :: t => loop(t, h :: acc)
}
loop(xs, Nil)
}
@main def run(): Unit =
println(reverse(List(1, 2, 3))) // List(3, 2, 1)Plusieurs accumulateurs
Une fonction auxiliaire peut transporter plusieurs accumulateurs à la fois.
Ici, nous suivons un produit intermédiaire et un compte dans la même boucle, puis nous renvoyons les deux sous forme de tuple.
Chacun transmet sa valeur mise à jour à l'appel suivant.
def stats(xs: List[Int]): (Int, Int) = {
def loop(rest: List[Int], prod: Int, count: Int): (Int, Int) =
rest match {
case Nil => (prod, count)
case h :: t => loop(t, prod * h, count + 1)
}
loop(xs, 1, 0)
}Choisir la valeur initiale
L'accumulateur initial doit être l'élément neutre de votre opération.
Pour une addition, utilisez 0 ; pour une multiplication, utilisez 1 ; pour construire une liste, utilisez Nil ; pour concaténer des chaînes, utilisez la chaîne vide.
Une mauvaise valeur initiale produit discrètement des réponses incorrectes.
// addition -> seed 0
// product -> seed 1
// list -> seed Nil
// string -> seed ""Ordre des résultats
La récursivité avec accumulateur traite les éléments de gauche à droite, mais un accumulateur qui ajoute au début les inverse.
Si vous devez conserver l'ordre en construisant une liste, inversez-la à la fin ou ajoutez les éléments à la fin, même si cette dernière approche est plus lente. Ajouter au début puis inverser est l'idiome habituel.
def mapInc(xs: List[Int]): List[Int] = {
def loop(rest: List[Int], acc: List[Int]): List[Int] = rest match {
case Nil => acc.reverse
case h :: t => loop(t, (h + 1) :: acc)
}
loop(xs, Nil)
}Vérification rapide
Choisissez l'affirmation exacte à propos de la récursivité avec accumulateur.
Récapitulatif
Un accumulateur transmet le résultat intermédiaire à travers les appels récursifs, afin que le cas de base puisse le renvoyer directement.
L'appel récursif se trouve ainsi en position terminale, ce qui permet l'optimisation des appels terminaux de Scala et la vérification de sécurité de @tailrec.
Initialisez l'accumulateur avec l'élément neutre de l'opération, puis inversez à la fin lorsque l'ordre est important.
Questions Fréquemment Posées
La leçon « Schémas d’accumulation » est-elle gratuite ?
Oui — le texte complet de « Schémas d’accumulation » 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 « Schémas d’accumulation » ?
Faites circuler l’état dans la récursion. 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 2 sur 4.
Combien de temps prend la leçon « Schémas d’accumulation » ?
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.
Toutes les leçons de ce cours
- Raisonner de façon récursive
- Schémas d’accumulation
- foldLeft et foldRight
- reduce et agrégation