La récursion terminale

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.

Laisser un commentaire

Votre adresse de messagerie ne sera pas publiée. Les champs obligatoires sont indiqués avec *

Vous pouvez utiliser ces balises et attributs HTML : <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>