Fonctions tailrec
Optimiser la récursivité
Fonctions tailrec est une leçon Kotlin Academy 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 Kotlin Academy, et ta progression se synchronise sur le web et l'application CoddyKit. Le cours Kotlin Academy comprend 4 leçons au total.
Qu'est-ce que la récursion terminale
Une fonction est récursive terminale lorsque son appel récursif constitue la toute dernière opération. Kotlin peut alors l'optimiser en boucle et éviter le dépassement de la pile.
tailrec fun countdown(n: Int) {
if (n < 0) return
println(n)
countdown(n - 1)
}
fun main() {
countdown(3)
}Le modificateur tailrec
Ajoutez le modificateur tailrec : le compilateur réécrit alors la récursion sous forme d'itération, avec un espace de pile constant.
tailrec fun sum(n: Int, acc: Int = 0): Int {
if (n == 0) return acc
return sum(n - 1, acc + n)
}
fun main() {
println(sum(100))
}Le modèle Accumulator
Pour transformer une récursion en forme terminale, transmettez les résultats dans un paramètre Accumulator, afin qu'il ne reste plus rien à calculer après l'appel.
tailrec fun factorial(n: Int, acc: Long = 1): Long {
if (n <= 1) return acc
return factorial(n - 1, acc * n)
}
fun main() {
println(factorial(10))
}Pourquoi l'appel doit être le dernier
Si quelque chose se produit après l'appel récursif (par exemple, multiplier son résultat), l'appel n'est pas en position terminale et ne peut pas être optimisé.
tailrec fun length(s: String, acc: Int = 0): Int {
if (s.isEmpty()) return acc
return length(s.drop(1), acc + 1)
}
fun main() {
println(length("hello"))
}Contre-exemple de récursion non terminale
Cette factorielle n'est NOT pas récursive terminale, car la multiplication a lieu après le retour de l'appel. La marquer avec tailrec générerait un avertissement.
fun badFactorial(n: Int): Long {
if (n <= 1) return 1
return n * badFactorial(n - 1)
}
fun main() {
println(badFactorial(5))
}Éviter le dépassement de la pile
Une récursion profonde sans tailrec peut provoquer un plantage. Avec ce modificateur, même les entrées volumineuses s'exécutent avec un espace de pile constant.
tailrec fun count(n: Int, acc: Int = 0): Int {
if (n == 0) return acc
return count(n - 1, acc + 1)
}
fun main() {
println(count(100000))
}Vérification par le compilateur
Si vous marquez une fonction avec tailrec alors que l'appel n'est pas en position terminale, le compilateur émet un avertissement et n'effectue pas l'optimisation. Tenez compte de cet avertissement.
tailrec fun gcd(a: Int, b: Int): Int {
if (b == 0) return a
return gcd(b, a % b)
}
fun main() {
println(gcd(48, 18))
}Récursion terminale ou boucle
Une fonction tailrec est compilée en produisant à peu près le même code que la boucle équivalente, tout en exprimant l'algorithme de manière récursive.
tailrec fun powerOfTwo(n: Int, acc: Long = 1): Long {
if (n == 0) return acc
return powerOfTwo(n - 1, acc * 2)
}
fun main() {
println(powerOfTwo(10))
}Plusieurs paramètres
Les fonctions récursives terminales transmettent souvent plusieurs paramètres d'état, tous mis à jour lors de l'appel récursif.
tailrec fun fib(n: Int, a: Long = 0, b: Long = 1): Long {
if (n == 0) return a
return fib(n - 1, b, a + b)
}
fun main() {
println(fib(20))
}Inverser avec tailrec
Un accumulateur peut construire un résultat tel qu'une chaîne inversée.
tailrec fun reverse(s: String, acc: String = ""): String {
if (s.isEmpty()) return acc
return reverse(s.drop(1), s.first() + acc)
}
fun main() {
println(reverse("kotlin"))
}Une recherche pratique
Les recherches itératives se transposent naturellement en récursion terminale.
tailrec fun indexOf(list: List<Int>, target: Int, i: Int = 0): Int {
if (i >= list.size) return -1
if (list[i] == target) return i
return indexOf(list, target, i + 1)
}
fun main() {
println(indexOf(listOf(5, 6, 7), 7))
}Vérification rapide
Vérifiez votre compréhension des fonctions tailrec.
Récapitulatif
Vous avez appris les fonctions tailrec :
tailrectransforme une récursion en position terminale en boucle, ce qui évite le dépassement de la pile.- L'appel récursif doit être la dernière opération.
- Utilisez un paramètre accumulateur pour obtenir une forme terminale.
- Le compilateur avertit lorsqu'une fonction ne peut pas être optimisée.
tailrec fun sum(n: Int, acc: Int = 0): Int =
if (n == 0) acc else sum(n - 1, acc + n)
fun main() {
println(sum(50))
}Questions Fréquemment Posées
La leçon « Fonctions tailrec » est-elle gratuite ?
Oui — le texte complet de « Fonctions 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 Kotlin Academy, passe à CoddyKit PRO. Le cours Kotlin Academy comprend 4 leçons au total.
Qu'est-ce que j'apprendrai dans « Fonctions tailrec » ?
Optimiser la récursivité Tu pratiques Kotlin Academy 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 Kotlin Academy ?
Aucune expérience préalable n'est requise. Kotlin Academy 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 « Fonctions 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 Kotlin Academy ?
Oui. Chaque leçon Kotlin Academy 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.