Bases de la récursivité
Fonctions récursives
Bases de la récursivité 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.
Qu’est-ce que 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. Elle convient naturellement à la programmation fonctionnelle, où elle remplace de nombreuses boucles par des définitions autoréférentielles.
Deux éléments essentiels
Toute fonction récursive correcte nécessite :
- Un cas de base qui arrête la récursion.
- Un cas récursif qui progresse vers le cas de base.
Sans cas de base atteignable, la récursion s’exécute indéfiniment.
Factorielle
L’exemple classique : n! = n * (n-1)!, avec 0! = 1 comme cas de base.
object Main {
def factorial(n: Int): Int =
if (n <= 1) 1
else n * factorial(n - 1)
def main(args: Array[String]): Unit = {
println(factorial(5))
}
}Suivre les appels
Chaque appel récursif se met en pause et attend le résultat interne. factorial(3) se développe en 3 * (2 * (1)). Les multiplications ont lieu lorsque les appels se terminent.
object Main {
def factorial(n: Int): Int = {
println(s"entering factorial($n)")
if (n <= 1) 1 else n * factorial(n - 1)
}
def main(args: Array[String]): Unit = {
println("result = " + factorial(3))
}
}Somme d’une liste
Récursion sur une liste : la somme correspond à la tête plus la somme de la queue, la somme de la liste vide étant égale à zéro.
object Main {
def sum(xs: List[Int]): Int = xs match {
case Nil => 0
case h :: t => h + sum(t)
}
def main(args: Array[String]): Unit = {
println(sum(List(1, 2, 3, 4)))
}
}Longueur d’une liste
Le même modèle permet de calculer la longueur : la liste vide vaut 0 ; sinon, il faut ajouter 1 à la longueur de la queue.
object Main {
def length[A](xs: List[A]): Int = xs match {
case Nil => 0
case _ :: t => 1 + length(t)
}
def main(args: Array[String]): Unit = {
println(length(List("a", "b", "c")))
}
}La pile d’appels
Chaque appel récursif en attente utilise une trame de pile. Une récursion profonde empile de nombreuses trames. Pour des entrées très volumineuses, cela peut épuiser la pile et lever une StackOverflowError.
Fibonacci
Certains problèmes se ramifient en plusieurs appels récursifs. Fibonacci s’appelle deux fois, ce qui est élégant, mais dont le coût est exponentiel.
object Main {
def fib(n: Int): Int =
if (n < 2) n
else fib(n - 1) + fib(n - 2)
def main(args: Array[String]): Unit = {
println(fib(10))
}
}Inverser une liste
La récursion peut construire de nouvelles structures : reverse ajoute la tête après avoir inversé la queue.
object Main {
def reverse[A](xs: List[A]): List[A] = xs match {
case Nil => Nil
case h :: t => reverse(t) :+ h
}
def main(args: Array[String]): Unit = {
println(reverse(List(1, 2, 3)))
}
}Récursivité ou itération
Les boucles modifient un compteur ; la récursion exprime le problème de manière déclarative. Les deux approches sont valides. La récursion excelle avec les données en forme d’arbre et les algorithmes diviser pour régner, mais une récursion naïve risque de provoquer un dépassement de pile pour les grandes entrées linéaires.
Plus grand diviseur commun
L’algorithme d’Euclide se prête naturellement à la récursion et converge rapidement.
object Main {
def gcd(a: Int, b: Int): Int =
if (b == 0) a else gcd(b, a % b)
def main(args: Array[String]): Unit = {
println(gcd(48, 18))
}
}Vérification rapide
Testez vos bases sur la récursivité.
Récapitulatif
Vous avez appris les bases de la récursion :
- Toute fonction récursive a besoin d’un cas de base et d’un cas récursif.
- Chaque appel en attente utilise une trame de pile ; une récursion profonde peut provoquer un dépassement de pile.
- La récursion permet d’exprimer naturellement les algorithmes sur les listes et les arbres.
Vous allez maintenant rendre la récursion sûre pour la pile grâce à l’annotation @tailrec.
Questions Fréquemment Posées
La leçon « Bases de la récursivité » est-elle gratuite ?
Oui — le texte complet de « Bases de la récursivité » 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 « Bases de la récursivité » ?
Fonctions 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 « Bases de la récursivité » ?
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
- Bases de la récursivité
- Annotation tailrec
- Motif de l’accumulateur
- Trampoline