La récursion terminale fait partie de la panoplie des outils d’un langage fonctionnel, même si elle peut être implémentée dans n’importe quel langage.
La récursion terminale est la capacité du compilateur à transformer une fonction récursive en une itération, c’est à dire une boucle. Pour que cela soit possible, il faut que l’appel récursif soit la dernière instruction de la méthode à être évaluée.
L’exemple ultra-classique du calcul de la factorielle
Voyons cela sur l’exemple récursif par excellence : le calcul de la factorielle, écrit en Scala :
def factorielle(n: Int): Int = {
if (n < 2) 1
else n * factorielle(n - 1)
}
factorielle(5)
La fonction ci-dessus est bien récursive, et visuellement, l’appel récursif est bien à la fin de la fonction. Mais cet appel récursif n’est pas la dernière instruction de la fonction, puisqu’il faut encore effectuer la multiplication une fois qu’on a obtenu la valeur de factorielle(n - 1)
.
C’est assez facile de transformer cette fonction pour que la récursion soit terminale :
def factorielle(n: Int, resultat: Int): Int = {
if (n < 2) resultat
else factorielle(n - 1, resultat * n)
}
factorielle(5, 1)
Le compilateur Scala va transformer cette fonction récursive en une boucle, équivalente au code suivant :
def factorielle(n: Int, resultat: Int) = {
var valeur = n
var res = resultat
while (valeur >= 2) {
res = res * valeur
valeur = valeur - 1
}
res
}
Détails Scala
Vous allez me dire que ce 2e argument, la valeur de départ qu’il faut mettre à 1, vous gêne. Moi aussi. De plus, il y a d’autres petites choses à faire, et nous allons régler tout ça.
En Scala, on peut annoter une méthode avec @tailrec
, ce qui fait que la compilation échoue si la méthode n’est pas récursive terminale. Vous avez ainsi la certitude qu’elle sera optimisée. De plus, une simple méthode d’une classe, pour avoir cette annotation, ne doit pas pouvoir être remplacée en dérivant la classe. C’est pourquoi le compilateur demande à ce que la méthode soit private
ou final
. En Scala, il est aussi possible de définir une méthode à l’intérieur d’une autre, ce qui règle ce problème. Il faut de plus définir le type du résultat de la méthode. Le moteur d’inférence de type de Scala ne s’en sort pas sinon. Tout ça mis ensemble pour le calcul de la factorielle donne :
def factorielle(n: Int): Int = {
import scala.annotation.tailrec
@tailrec
def fact(n: Int, resultat: Int): Int =
if (n < 2) resultat
else fact(n - 1, resultat * n)
fact(n, 1)
}
factorielle(5)
J’ai aussi mis le import
à l’intérieur de la méthode, mais vous pouvez le déplacer en début du fichier.
Intérêts
Il y a plusieurs intérêts à utiliser la récursion terminale lorsque c’est possible. D’abord, cela permet d’écrire du code sans utiliser de variables mutables.
Ensuite, cela permet de comprendre très simplement ce qui est fait, parce que le corps de la méthode ne traite toujours qu’une seule itération. Il n’y a aucun code pour gérer l’ensemble des itérations.
Avec la récursion terminale, on profite des avantages de la récursivité, sans les inconvénients.
Exemple : donner n nombres dont le total donne m
Un dernier exemple : vous devez fournir une liste de n
nombres au hasard dont le total donne m
. Aucun nombre ne doit être égal à 0
, mais plusieurs de ces nombres peuvent être égaux. Voici comment vous pourriez l’écrire :
def listeNombres(combien: Int, total: Int): List[Int] = {
val random = new scala.util.Random()
@scala.annotation.tailrec
def hasard(n: Int, listeTrouve: List[Int]): List[Int] =
if (n == 0) listeTrouve
else {
val i = random.nextInt(total - 2) + 1
if (listeTrouve.contains(i)) hasard(n, listeTrouve)
else hasard(n - 1, i +: listeTrouve)
}
val intervalles = hasard(combien - 1, List(total)).sorted
@scala.annotation.tailrec
def calcDiff(
precedent: Int, aTraiter: List[Int], resultat: List[Int]): List[Int] =
if (aTraiter.size == 0) resultat
else calcDiff(
aTraiter.head, aTraiter.tail, resultat :+ (aTraiter.head - precedent))
nombres(0, intervalles, List())
}
listeNombres(4, 100).foreach(println)
On cherche d’abord n-1
nombres différents, compris entre 1 et m-1
inclus, avec la méthode récursive hasard
. On trie cette liste et on y ajoute 0
et m
, ce qui définit n
intervalles dont le total est m
. On crée ensuite la liste des nombres demandés avec une 2e méthode récursive calcDiff
, qui calcule les différences.