0Pricing
Scala for Backend Engineering & Functional Programming · Leçon

Raisonner de façon récursive

Cas de base et étapes récursives.

Raisonner de façon récursive est une leçon Scala for Backend Engineering & Functional Programming gratuite sur CoddyKit. Ceci est la leçon 1 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.

Que signifie la récursivité

La récursivité désigne le fait qu’une fonction s’appelle elle-même pour résoudre une version plus petite du même problème.

En Scala, la récursivité convient naturellement à la programmation fonctionnelle, car elle permet d’exprimer des boucles sans variables modifiables.

Toute fonction récursive a besoin de deux éléments : un moyen de s’arrêter et un moyen de réduire le problème.

Commencer par le cas de base

Le cas de base est l’entrée la plus simple à laquelle la fonction peut répondre directement, sans récursivité supplémentaire.

Sans cas de base, la fonction s’appellerait indéfiniment et provoquerait un dépassement de pile.

Concevez toujours le cas de base avant l’étape récursive.

def countdown(n: Int): Unit =
  if (n < 0) ()           // base case: stop
  else {
    println(n)
    countdown(n - 1)      // recursive step
  }

Une première fonction récursive

Voici un programme complet qui additionne les nombres de 1 à n.

Le cas de base renvoie 0 ; le cas récursif ajoute n à la somme de tous les nombres inférieurs.

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

@main def run(): Unit =
  println(sum(5))   // 15

Suivre les appels

Pour comprendre la récursivité, développez les appels à la main.

sum(3) devient 3 + sum(2), qui devient 3 + 2 + sum(1), puis 3 + 2 + 1 + sum(0).

Ce n’est que lorsque sum(0) renvoie 0 que la chaîne se réduit à une seule valeur : 6.

// sum(3)
// = 3 + sum(2)
// = 3 + (2 + sum(1))
// = 3 + (2 + (1 + sum(0)))
// = 3 + (2 + (1 + 0))
// = 6

Récursivité sur les listes

Les listes sont récursives par nature : une liste est soit vide (Nil), soit composée d’une tête suivie d’une queue plus petite.

Cette structure s’adapte directement aux fonctions récursives. La liste vide constitue le cas de base ; la tête et la récursivité appliquée à la queue constituent l’étape récursive.

def length[A](xs: List[A]): Int = xs match {
  case Nil     => 0
  case _ :: t  => 1 + length(t)
}

Appliquer le filtrage de motifs à la queue

Le motif :: sépare une liste non vide en sa tête et sa queue.

Chaque appel récursif porte sur une liste strictement plus courte, ce qui garantit une progression vers Nil.

C’est la manière classique de parcourir récursivement une liste en Scala.

def sumList(xs: List[Int]): Int = xs match {
  case Nil    => 0
  case h :: t => h + sumList(t)
}

@main def run(): Unit =
  println(sumList(List(1, 2, 3, 4)))  // 10

Deux appels récursifs

Certains problèmes se ramifient en plusieurs appels récursifs.

L’exemple classique est Fibonacci, où chaque valeur dépend des deux valeurs précédentes.

Cette version naïve est simple, mais lente, car elle recalcule souvent les mêmes valeurs.

def fib(n: Int): Int =
  if (n < 2) n
  else fib(n - 1) + fib(n - 2)

@main def run(): Unit =
  println(fib(7))   // 13

Le coût sur la pile

Chaque appel récursif ajoute une trame à la pile d’appels, qui doit attendre le retour de l’appel interne.

Pour une récursivité très profonde, cela peut épuiser la pile et déclencher une StackOverflowError.

Compter la profondeur, et pas seulement la taille, vous aide à prévoir ce risque.

// This would overflow the stack for large n:
// def deep(n: Int): Int =
//   if (n == 0) 0 else 1 + deep(n - 1)
// deep(1000000)  // StackOverflowError

Réduire le problème vers le cas de base

L’invariant essentiel de la récursivité est que chaque appel doit se rapprocher du cas de base.

Si l’argument ne diminue pas ou n’atteint jamais la condition d’arrêt, la récursivité ne se termine jamais.

Vérifiez cela avant toute exécution.

def reverse[A](xs: List[A]): List[A] = xs match {
  case Nil    => Nil
  case h :: t => reverse(t) :+ h   // t is smaller than xs
}

Récursivité ou boucles

Le code impératif utilise des boucles while avec des compteurs modifiables ; le code fonctionnel utilise la récursivité avec des valeurs immuables.

Les deux peuvent exprimer les mêmes calculs, mais la récursivité décrit plus directement la structure des données.

En Scala, vous préférerez souvent la récursivité ou les fonctions d'ordre supérieur aux boucles brutes.

// Imperative
var total = 0
for (i <- 1 to 5) total += i

// Recursive
def sum(n: Int): Int = if (n == 0) 0 else n + sum(n - 1)

Concevoir une solution récursive

Une méthode fiable consiste à identifier le cas de base, à supposer que l'appel récursif fonctionne déjà sur l'entrée plus petite, puis à combiner la tête avec ce résultat.

Ce saut de confiance est au cœur du raisonnement récursif. Vous faites confiance à l'appel sur une entrée plus petite et ne gérez qu'une seule étape.

def maxOf(xs: List[Int]): Int = xs match {
  case h :: Nil => h
  case h :: t   => math.max(h, maxOf(t))
}

@main def run(): Unit =
  println(maxOf(List(3, 9, 2, 7)))  // 9

Vérification rapide

Testez votre compréhension de la structure récursive.

Récapitulatif

La récursivité résout un problème en le réduisant à une instance plus petite de lui-même.

Toute fonction récursive a besoin d'un cas de base pour s'arrêter et d'une étape récursive qui rapproche l'entrée de ce cas de base en la réduisant.

Les listes, avec leur structure Nil et tête-queue, sont un terrain idéal pour le raisonnement récursif. Surveillez la profondeur de la pile avec des entrées très volumineuses.

Questions Fréquemment Posées

La leçon « Raisonner de façon récursive » est-elle gratuite ?

Oui — le texte complet de « Raisonner de façon récursive » 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 « Raisonner de façon récursive » ?

Cas de base et étapes récursives. 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 1 sur 4.

Combien de temps prend la leçon « Raisonner de façon récursive » ?

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

  1. Raisonner de façon récursive
  2. Schémas d’accumulation
  3. foldLeft et foldRight
  4. reduce et agrégation
← Retour à Scala for Backend Engineering & Functional Programming