Scala for Backend Engineering & Functional Programming · Leçon

Annotation tailrec

Optimisation garantie

Annotation tailrec 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.

Qu’est-ce que la récursion terminale ?

Un appel récursif est en position terminale lorsqu’il constitue la toute dernière action de la fonction. Une fonction récursive terminale peut être optimisée en boucle et réutiliser une seule trame de pile, ce qui empêche tout dépassement de pile.

Position terminale

Dans n * factorial(n-1), l’appel récursif n’est pas le dernier : la multiplication a lieu après son retour. Dans gcd(b, a % b), l’appel est le dernier. Seul ce dernier appel est récursif terminal.

L’annotation @tailrec

Importez scala.annotation.tailrec et annotez une méthode. Le compilateur vérifie alors que l’appel est véritablement en position terminale et applique l’optimisation. Si ce n’est pas le cas, la compilation échoue.

import scala.annotation.tailrec

object Main {
  @tailrec
  def countdown(n: Int): Unit = {
    if (n >= 0) {
      println(n)
      countdown(n - 1)
    }
  }

  def main(args: Array[String]): Unit = countdown(3)
}

Optimisation garantie

Le principal avantage de @tailrec est la garantie à la compilation. Vous êtes immédiatement averti si votre fonction n’est pas sûre pour la pile, au lieu de le découvrir à la suite d’un plantage à l’exécution avec une entrée volumineuse.

Un gcd récursif terminal

L’algorithme d’Euclide est déjà récursif terminal : l’appel récursif constitue le résultat complet du corps de la fonction. L’annotation le confirme.

import scala.annotation.tailrec

object Main {
  @tailrec
  def gcd(a: Int, b: Int): Int =
    if (b == 0) a else gcd(b, a % b)

  def main(args: Array[String]): Unit = {
    println(gcd(1071, 462))
  }
}

Ce qui rompt la position terminale

Voici des schémas courants qui font sortir l’appel de la position terminale :

Effectuer un calcul arithmétique sur le résultat : n + f(...).
Envelopper l’appel dans un constructeur : x :: f(...).
Utiliser le résultat dans un bloc try.

Exemple non terminal

Cette somme n’est pas récursive terminale, car l’addition enveloppe l’appel. L’annoter avec @tailrec provoquerait une erreur de compilation. (Elle est présentée sans l’annotation pour pouvoir s’exécuter.)

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

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

Pourquoi l’optimisation est impossible

Comme n + sum(n - 1) doit mémoriser n pour terminer l’addition après le retour de l’appel, chaque niveau a besoin de sa propre trame de pile. Le compilateur ne peut pas transformer cela en boucle : la fonction n’est donc pas récursive terminale.

Une grande boucle récursive terminale

Une somme récursive terminale utilisant un accumulateur s’exécute avec des entrées très volumineuses sans provoquer de dépassement de pile, car elle réutilise une seule trame.

import scala.annotation.tailrec

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

  def main(args: Array[String]): Unit = {
    println(sumTo(1000000))
  }
}

tailrec exige final ou local

Pour que @tailrec s’applique, la méthode ne doit pas pouvoir être redéfinie : elle doit être private, final ou être une méthode locale ou imbriquée. Une méthode ouverte pourrait être redéfinie, ce qui compromettrait l’optimisation ; le compilateur la rejette donc.

Particularité de la récursion mutuelle

@tailrec optimise uniquement une fonction qui s’appelle elle-même. Deux fonctions qui s’appellent mutuellement ne peuvent pas être optimisées comme récursion terminale directement par la JVM ; il faut utiliser la transformation par trampoline, présentée plus loin.

Vérification rapide

Vérifiez votre compréhension de @tailrec.

Récapitulatif

Vous avez appris l’annotation @tailrec :

Un appel en position terminale peut être optimisé en boucle.
@tailrec fournit une garantie de sûreté de la pile à la compilation.
La méthode doit être final, private ou locale.
L’annotation ne concerne que la récursion sur soi-même, pas la récursion mutuelle.

Questions Fréquemment Posées

La leçon « Annotation tailrec » est-elle gratuite ?

Oui — le texte complet de « Annotation tailrec » 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 « Annotation tailrec » ?

Optimisation garantie 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 « Annotation tailrec » ?

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