Scala for Backend Engineering & Functional Programming · Leçon

Motif de l’accumulateur

Convertissez en récursion terminale

Motif de l’accumulateur est une leçon Scala for Backend Engineering & Functional Programming gratuite sur CoddyKit. Ceci est la leçon 3 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.

Le schéma de l’accumulateur

Le schéma de l’accumulateur transforme une fonction non récursive terminale en fonction récursive terminale. Vous transportez le résultat partiel dans un paramètre supplémentaire, l’accumulateur, au lieu de le construire après le retour de l’appel.

L’idée centrale

Au lieu de n + sum(n-1) (travail effectué après l’appel), vous calculez le nouveau total partiel avant l’appel : sum(n-1, acc + n). L’appel récursif devient alors la dernière action.

Avant : somme non terminale

Cette version directe n’est pas récursive terminale : l’addition attend le retour de l’appel récursif.

object Main {
  def sum(n: Int): Int =
    if (n == 0) 0 else n + sum(n - 1)

  def main(args: Array[String]): Unit = {
    println(sum(50))
  }
}

Après : somme terminale avec accumulateur

Ajoutez un paramètre acc qui contient le total courant. L’appel récursif est désormais en position terminale et peut être optimisé.

import scala.annotation.tailrec

object Main {
  @tailrec
  def sum(n: Int, acc: Int = 0): Int =
    if (n == 0) acc else sum(n - 1, acc + n)

  def main(args: Array[String]): Unit = {
    println(sum(50))
  }
}

Factorielle récursive terminale

Appliquez la même transformation à factorial : multipliez dans l’accumulateur avant de poursuivre la récursion.

import scala.annotation.tailrec

object Main {
  @tailrec
  def factorial(n: Int, acc: Long = 1): Long =
    if (n <= 1) acc else factorial(n - 1, acc * n)

  def main(args: Array[String]): Unit = {
    println(factorial(10))
  }
}

Masquer l’accumulateur

Le paramètre supplémentaire est un détail d’implémentation. Enveloppez la fonction auxiliaire récursive terminale dans une fonction publique claire afin que les appelants ne voient pas acc.

import scala.annotation.tailrec

object Main {
  def factorial(n: Int): Long = {
    @tailrec
    def loop(m: Int, acc: Long): Long =
      if (m <= 1) acc else loop(m - 1, acc * m)
    loop(n, 1)
  }

  def main(args: Array[String]): Unit = {
    println(factorial(6))
  }
}

Accumuler une liste

Ce schéma permet également de construire des collections. Une inversion récursive terminale ajoute chaque tête en tête de la liste accumulateur.

import scala.annotation.tailrec

object Main {
  def reverse[A](xs: List[A]): List[A] = {
    @tailrec
    def loop(rem: List[A], acc: List[A]): List[A] = rem match {
      case Nil    => acc
      case h :: t => loop(t, h :: acc)
    }
    loop(xs, Nil)
  }

  def main(args: Array[String]): Unit = {
    println(reverse(List(1, 2, 3, 4)))
  }
}

Ordre de l’accumulation

Notez que l’ajout en tête de l’accumulateur inverse naturellement l’ordre. Pour une fonction de construction de liste qui conserve l’ordre, vous construisez souvent la liste inversée puis vous l’inversez à la fin, ou vous utilisez une structure d’ajout efficace.

map récursif terminal

Construisez une liste résultat avec un accumulateur, puis inversez-la une seule fois à la fin pour rétablir l’ordre.

import scala.annotation.tailrec

object Main {
  def mapTail[A, B](xs: List[A])(f: A => B): List[B] = {
    @tailrec
    def loop(rem: List[A], acc: List[B]): List[B] = rem match {
      case Nil    => acc.reverse
      case h :: t => loop(t, f(h) :: acc)
    }
    loop(xs, Nil)
  }

  def main(args: Array[String]): Unit = {
    println(mapTail(List(1, 2, 3))(_ * 10))
  }
}

Relation avec foldLeft

Le schéma de l’accumulateur est exactement ce que généralise foldLeft : il fait circuler un accumulateur dans une collection de manière récursive terminale. De nombreuses fonctions manuelles utilisant un accumulateur peuvent être réécrites avec un seul foldLeft.

@main def run(): Unit = {
  val total = List(1, 2, 3, 4).foldLeft(0)(_ + _)
  println(total)
}

Quand l’utiliser

Utilisez le schéma de l’accumulateur lorsqu’une fonction récursive traite une grande structure linéaire et provoquerait sinon un dépassement de pile. Vous échangez une structure légèrement moins évidente contre une sûreté de pile garantie.

Vérification rapide

Vérifiez votre maîtrise du schéma de l’accumulateur.

Récapitulatif

Vous avez appris le schéma de l’accumulateur :

Transporter le résultat partiel dans un paramètre supplémentaire.
Le calculer avant la récursion pour atteindre la position terminale.
Masquer l’accumulateur derrière une fonction publique claire.
Le généraliser avec foldLeft.

Questions Fréquemment Posées

La leçon « Motif de l’accumulateur » est-elle gratuite ?

Oui — le texte complet de « Motif de l’accumulateur » 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 « Motif de l’accumulateur » ?

Convertissez en récursion terminale 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 3 sur 4.

Combien de temps prend la leçon « Motif de l’accumulateur » ?

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

← Retour à Scala for Backend Engineering & Functional Programming