Archives mensuelles : février 2015

La récursion terminale

Laisser une réponse

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.

La signature de la classe Enum en Java

Laisser une réponse

Lorsqu’on déclare un énuméré en Java, par exemple

enum Couleur { Rouge, Vert, Bleu }

c’est en fait comme si on déclarait une classe dérivée de la classe Enum, qui est définie dans le JRE. Nous allons nous intéresser à la signature de cette classe Enum, en fait la construire par étape, avec les explications.

1re tentative

class Enum { … }
class Couleur extends Enum { … }

Ça pourrait fonctionner, sauf que la classe Enum permet d’ordonner les éléments de l’énuméré. Pour faire ça, elle implémente l’interface Comparable<E>

2e tentative

class Enum<E> implements Comparable<E> { … }
class Couleur extends Enum<Couleur> { … }

Pour fournir le type E à Comparable, il faut que Enum soit aussi générique. Il est clair que c’est des éléments de type Couleur que l’on veut comparer. C’est pour cette raison que dans l’exemple, on fournit le type Couleur lui même à la classe Enum.

Ça pourrait déjà fonctionner ainsi. Le problème de cette tentative est que rien n’empêche de mettre une autre classe comme type générique à Enum. Avec cette signature, nous pourrions écrire :

class Couleur extends Enum<Boolean> { … }

ce qui poserait des problèmes pour la comparaison de 2 couleurs.

En fait, il faut que le type générique passé à Enum soit un Enum lui-même.

3e tentative

class Enum<E extends Enum> implements Comparable<E> { … }

Nous nous approchons. Le seul souci, c’est que Enum prenant un type en paramètre, il faut le fournir aussi lorsqu’on écrit <E extends Enum>.

4e tentative

class Enum<E extends Enum<F>> implements Comparable<E> { … }

Là, on indique que le type paramétré doit lui-même être un énuméré, mais il est possible que ce soit un autre énuméré, et pas le type que nous sommes en train de créer nous même. En supposant que le type Langue soit un énuméré existant, on pourrait donc écrire :

class Couleur extends Enum<Langue> { … }

Cela évite déjà de mettre énormément de type à la place de Langue, mais ce n’est pas suffisant.

5e tentative

class Enum<E extends Enum<E>> implements Comparable<E> { … }

La seule différence par rapport à la tentative précédente, est que le type F est remplacé par le type E lui-même. Ce qui finalement, semble même plus simple que la tentative précédente.

Nous avons maintenant la signature correcte du type Enum, tel qu’il existe dans l’API Java.

Ce que j’en tire

Lorsqu’on voit pour la 1re fois la signature réelle du type Enum, on se dit qu’elle est compliquée, que nous aurions été incapable de l’écrire. Mais en la décortiquant comme nous venons de le faire, on comprends en fait très bien ce qui se passe.

L’autre remarque, c’est que tous les langages ont des aspects compliqués, même Java. Mais pour le code que nous écrivons tous les jours, nous pouvons ignorer ces aspects qui ne nous concernent que très rarement. Il n’est en général nécessaire de les maîtriser que si on écrit une librairie ou un framework.

Et pour finir sur un clin d’œil, il y a en Java des choses bien plus compliquées encore. Et cela donne raison à la devise du blog : « Tout est toujours plus compliqué qu’on ne croit, même en tenant compte de cette loi. »