Récursivité

Fonctions récursives simples

Notion de récursivité

Exemple : la fonction factorielle, définie en mathématiques par

Justification : le calcul se termine toujours (par $0!$), donc la définition est bien fondée.

En Caml

Traduisons directement :

let fact n =
  if n = 0 then 1
  else n * fact (n - 1) ;;

Quel est le problème ? Pourquoi ?

Portée statique et définitions récursives

• En mathématiques, on ne peut parler d'une entité avant d'en avoir donné la définition. La même chose est vraie en Caml.
• Pour une occurrence quelconque d'un nom, il suffit d'examiner le texte du programme qui précède pour trouver la liaison qui l'a défini. Cette liaison est soit une définition (let), soit un paramètre de fonction.

let x = 1 ;;
let x = x + 1 ;;

Dans la seconde ligne, le x de droite désigne le x défini avant, qui vaut 1. De même, dans let f x = x + 1, le x du corps désigne le paramètre.

La construction let rec

Voilà où était le souci : nous utilisions fact avant de l'avoir défini. Lorsqu'on écrit let f = …, une occurrence de f dans la partie droite ne désigne pas le f qu'on est en train de définir, mais une définition précédente de f, s'il y en a une. Ici, il n'y en avait pas.

Une simple construction let ne permet donc pas de définir une fonction récursive. On utilise let rec :

let rec fact n =
  if n = 0 then 1
  else n * fact (n - 1) ;;
fact 3 ;;
fact 10 ;;

Simulation : comment ça marche ?

Déroulons fact 3 :

Chaque appel attend le résultat du suivant pour faire sa multiplication. Les multiplications ne se font qu'au retour, une fois atteint le cas fact 0.

L'essentiel

Définitions

Règles à retenir

Que se passe-t-il si on oublie le cas d'arrêt de la fonction factorielle ?

let rec fact_sans_arret n = n * fact_sans_arret (n - 1) ;;
fact_sans_arret 3 ;;

Sans cas d'arrêt, la fonction ne peut pas s'arrêter : elle ne termine pas. On parle de récursion infinie. Chaque appel en attente occupe un peu de mémoire (la pile), et le programme finit par en manquer.

Le cas d'arrêt ne suffit pas. Appelons la bonne fact sur un nombre négatif :

fact (-1) ;;

De $-1$, on passe à $-2$, $-3$… : on s'éloigne de 0 au lieu de s'en approcher.

Pour fact, il faudrait refuser les négatifs, par exemple par if n < 0 then invalid_arg "fact".

Forme générale d'une fonction récursive

L'écriture d'une fonction récursive suivra bien souvent ce schéma :

let rec f x =
  if condition_arret then
    expression_arret
  else
    expression_avec_un_appel_recursif

Le filtrage peut bien entendu être utilisé à la place de l'alternative.

À l'endroit et à l'envers

Écrire en Caml une fonction dont la définition mathématique est récurrente est quasi immédiat : c'est une simple traduction. Voyons maintenant des problèmes un peu différents.

Exemple du compte à rebours

On veut une fonction qui affiche les nombres par ordre décroissant jusqu'à 1, à partir d'une certaine limite : pour 5, on veut voir 5 4 3 2 1 à l'écran.

Comment résoudre ce problème de façon récursive ? Il faut trouver un équivalent de la définition par récurrence : exprimer le problème en fonction du même problème, sur des données « plus petites ».

Mode d'emploi

1. D'abord, la spécification précise du problème : afficher en ordre décroissant les entiers compris entre 1 et $n$.
2. Ensuite, l'équation de récurrence, en fonction de problèmes « connus ». Afficher en ordre décroissant les entiers compris entre 1 et $n$, c'est :
3. afficher $n$ ;
4. puis afficher en ordre décroissant les entiers compris entre 1 et $n - 1$.
5. Enfin, le cas d'arrêt, sans lequel la définition ne serait pas complète : afficher en ordre décroissant les entiers compris entre 1 et 0, c'est ne rien faire !

La fonction

let rec countdown n =
  if n = 0 then ()
  else begin
    print_int n ; print_string " " ;
    countdown (n - 1)
  end ;;
countdown 5 ;;

La seule difficulté est de considérer le problème comme déjà résolu pour les données plus petites, pour pouvoir s'en servir dans l'expression de la solution, et ainsi le résoudre !

Et dans l'autre sens ?

Dans countdown, on affiche l'entier, puis on fait l'appel récursif. Que se passe-t-il si l'on fait d'abord l'appel récursif, avant d'afficher $n$ ?

let rec count n =
  if n = 0 then ()
  else begin
    count (n - 1) ;
    print_int n ; print_string " "
  end ;;

À votre avis, que se passera-t-il à l'appel count 5 ?

count 5 ;;

Pourquoi ?

Déroulons count 3 : pour afficher 3, il faut d'abord terminer count 2, qui doit d'abord terminer count 1, qui doit d'abord terminer count 0 (qui ne fait rien). Puis count 1 affiche 1 et se termine, count 2 affiche 2, et enfin count 3 affiche 3.

Plusieurs appels récursifs

Fonctions à plusieurs appels

La suite de Fibonacci est définie par :

Sa traduction en Caml comporte deux appels récursifs :

let rec fibo n =
  if n <= 1 then 1
  else fibo (n - 1) + fibo (n - 2) ;;
fibo 10 ;;

Appels imbriqués

La fonction d'Ackermann est un autre exemple de fonction à plusieurs appels. Elle est définie par :

Ici, un appel récursif sert d'argument à un autre :

let rec ackermann m n =
  if m = 0 then n + 1
  else if n = 0 then ackermann (m - 1) 1
  else ackermann (m - 1) (ackermann m (n - 1)) ;;
ackermann 2 3 ;;
ackermann 3 3 ;;

Cette fonction termine toujours, mais elle croît extraordinairement vite : $A(4, 2)$ a près de 20 000 chiffres.

Récursivité croisée

On peut définir la parité de la manière suivante :

• 0 est pair ;
• $n$ est pair si $n - 1$ est impair.

De la même manière :

• 0 n'est pas impair ;
• $n$ est impair si $n - 1$ est pair.

Quel sera le souci ?

let rec pair n = if n = 0 then true else impair (n - 1) ;;

pair utilise impair, qui utilise pair : aucune des deux ne peut être définie avant l'autre. On les définit ensemble, avec let rec … and … :

let rec pair n = if n = 0 then true else impair (n - 1)
and impair n = if n = 0 then false else pair (n - 1) ;;
pair 10 ;;
impair 7 ;;

Pour aller plus loin

Efficacité

Écrire une fonction qui « marche » ne suffit pas forcément pour résoudre un problème : il faut aussi le faire efficacement. Trouver une solution efficace à un problème, c'est trouver un algorithme rapide. Mais comment évaluer le temps d'exécution d'une fonction ?

Un peu de complexité

• On détermine, en fonction de la taille des données, le nombre d'opérations effectuées.
• On pourrait compter les tests, les additions, les soustractions… ou se contenter de compter les appels récursifs : la mesure obtenue est la même, à un facteur près.

Par exemple, pour la somme des entiers de 1 à $n$ :

let rec somme n = if n = 0 then 0 else n + somme (n - 1) ;;
somme 100 ;;

Combien d'appels pour le calcul de somme n ? Un par valeur de $n$, $n - 1$, …, 0 : $n + 1$ appels. La complexité est linéaire en $n$.

Ordre de grandeur

Savoir si la complexité est $n$ ou $n + 1$ n'a pas d'importance ; en revanche, $n$ ou $n^2$, si ! Les ordres de grandeur usuels, du plus rapide au plus lent :

1. $1$ : constant ;
2. $\log n$ : logarithmique ;
3. $n$ : linéaire ;
4. $n \log n$ ;
5. $n^2$ : quadratique ;
6. $n^a$ : polynomial ;
7. $2^n$, $e^n$ : exponentiel.

De plus, la complexité dépend souvent des données elles-mêmes, pas seulement de leur taille. On distingue la complexité dans le meilleur des cas, dans le pire des cas, et en moyenne.

Un exemple classique : le calcul de la puissance

Comparons

let rec power x n =
  if n = 0 then 1
  else x * power x (n - 1) ;;

et

let rec fast_power x n =
  if n = 0 then 1
  else fast_power (x * x) (n / 2) * (if n mod 2 = 0 then 1 else x) ;;
power 2 10 ;;
fast_power 2 10 ;;

La seconde repose sur $x^{2k} = (x^2)^k$ et $x^{2k+1} = (x^2)^k \times x$.

Combien d'appels dans chaque cas ? power x n fait $n + 1$ appels : complexité linéaire. fast_power x n divise $n$ par 2 à chaque appel : pour $n = 10$, les appels se font avec $n = 10, 5, 2, 1, 0$, soit 5 appels. En général, environ $\log_2 n$ appels : complexité logarithmique. Pour $n = 1\,000\,000$, c'est 21 appels au lieu d'un million.

Plusieurs appels : Fibonacci

Calculer la complexité d'une fonction qui ne comporte qu'un appel récursif ne semble pas compliqué. Qu'en est-il des fonctions à plusieurs appels ?

let rec fibo = function
  | 0 | 1 -> 1
  | n -> fibo (n - 1) + fibo (n - 2) ;;

Dessinons l'arbre des appels de fibo 4 : fibo 4 appelle fibo 3 et fibo 2 ; fibo 3 appelle fibo 2 et fibo 1 ; chaque fibo 2 appelle fibo 1 et fibo 0. Soit 9 appels, et fibo 2 est calculé deux fois.

Soit $R_n$ le nombre d'appels à fibo pour calculer fibo n. On a $R_0 = R_1 = 1$ et $R_n = 1 + R_{n-1} + R_{n-2}$ ; on montre par récurrence que $R_n = 2 \times \mathit{fibo}(n) - 1$. Or $\mathit{fibo}(n)$ croît exponentiellement (environ $1{,}618^n$) : la complexité est exponentielle. fibo 40 demande plus de 300 millions d'appels.

Peut-on faire mieux ?

Comment calculer fibo 10 à la main ? Personne ne dessine l'arbre des appels. On écrit la suite dans l'ordre : 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89. Chaque terme est la somme des deux précédents, qu'on vient d'écrire.

C'est l'idée : voir le problème dans « l'autre sens ».

• Plutôt que de calculer le terme de rang $n$ en fonction des deux précédents, on calcule le terme de rang 2, puis les suivants.
• Il suffit de conserver les deux derniers termes calculés pour calculer le nouveau.
• Il faut aussi savoir à quel rang on en est : un paramètre $i$ servira de compteur, augmenté à chaque appel, et on s'arrêtera dès qu'il vaudra $n$.
• Les deux autres paramètres de la fonction récursive sont le terme courant (au rang $i$) et le terme précédent.

Fibonacci, en linéaire !

let fibo n =
  if n < 0 then
    failwith "fibo : rang négatif !"
  else
    let rec fib i fi fi_1 =
      if i >= n then fi
      else fib (i + 1) (fi + fi_1) fi
    in
    fib 1 1 1 ;;
fibo 10 ;;
fibo 80 ;;

fib fait au plus $n$ appels : la complexité est linéaire. fibo 80 est immédiat, alors que la version précédente n'aurait pas fini de sitôt.

Un classique : les tours de Hanoï

À la fin du XIXᵉ siècle, le mathématicien français Édouard Lucas (1883) invente la légende suivante : « Dans le grand temple de Bénarès, sous le dôme qui marque le centre du monde, repose un socle de cuivre équipé de trois aiguilles verticales en diamant de 50 cm de haut. À la création, Dieu enfila 64 plateaux en or pur sur une des aiguilles, le plus grand en bas et les autres de plus en plus petits. C'est la tour de Brahmâ. Les moines doivent continûment déplacer les disques de manière que ceux-ci se retrouvent dans la même configuration sur une autre aiguille. La règle de Brahmâ est simple : un seul disque à la fois et jamais un grand plateau sur un plus petit. Arrivé à ce résultat, le monde tombera en poussière et disparaîtra. »

Le but du jeu est de déplacer tous les disques du piquet « source » vers un autre piquet (la « destination »), en se servant du piquet « intermédiaire », et en respectant les règles suivantes :

• on ne peut déplacer qu'un disque à la fois ;
• on ne peut pas déplacer un disque qui se trouve sous un autre ;
• un disque ne peut être déposé sur un disque plus petit.

Quel est le nombre minimum de déplacements nécessaires pour déplacer une pile de $n$ disques ?

La solution

Méthode :

• problème : déplacer $n$ disques, du piquet source vers le piquet destination ;
• cas de base : déplacer 0 disque, c'est ne rien faire ;
• hypothèse : on sait « déplacer $n - 1$ disques du piquet $i$ au piquet $j$ » ;
• équation de récurrence : pour déplacer $n$ disques du piquet source vers le piquet destination, il suffit de :
• déplacer $n - 1$ disques du piquet source au piquet intermédiaire ;
• déplacer 1 disque (le plus grand) du piquet source au piquet destination ;
• déplacer $n - 1$ disques du piquet intermédiaire au piquet destination.

L'implantation

La fonction hanoi a 3 paramètres :

• n : le nombre de disques ;
• source : le numéro du piquet de départ ;
• destination : le numéro du piquet d'arrivée.

Il faut aussi connaître le piquet intermédiaire : c'est 6 - source - destination, puisque $1 + 2 + 3 = 6$ !

let rec hanoi n source destination =
  if n > 0 then begin
    let intermediaire = 6 - source - destination in
    hanoi (n - 1) source intermediaire ;
    print_int source ; print_string " -> " ; print_int destination ;
    print_newline () ;
    hanoi (n - 1) intermediaire destination
  end ;;
hanoi 3 1 3 ;;

Pour 3 disques, 7 déplacements. Si $D_n$ est le nombre de déplacements pour $n$ disques, $D_0 = 0$ et $D_n = 2D_{n-1} + 1$, d'où $D_n = 2^n - 1$. Et on ne peut pas faire mieux : pour déplacer le plus grand disque, il faut que les $n - 1$ autres soient tous sur le piquet intermédiaire.

Pour les 64 disques de la légende, $2^{64} - 1 \approx 1{,}8 \times 10^{19}$ déplacements : à un déplacement par seconde, près de 600 milliards d'années. Le monde a encore un peu de temps.

Indécidabilité de la terminaison

Alan Turing a démontré en 1936 qu'il est impossible d'écrire un programme qui teste si une fonction termine son calcul. L'arrêt d'un calcul est indécidable. On va le montrer avec une petite histoire.

Il était une fois…

Un professeur d'algorithmique en a assez des fonctions Caml de ses étudiants qui ne s'arrêtent pas. Cela l'oblige chaque fois à des manipulations compliquées pour stopper ces programmes. Il voit alors dans un journal spécialisé la publicité suivante :

…et puis…

Impressionné par la publicité, le professeur achète à prix d'or cette petite merveille, et pense que sa vie d'enseignant va enfin être tranquille.

Un élève lui fait toutefois remarquer qu'il ne comprend pas l'acquisition faite, et lui montre la fonction suivante :

let termine f = (* contenu breveté par le vendeur *) ;;

let rec absurde () =
  if termine absurde then absurde ()
  else () ;;

absurde termine-t-elle ?

• Si termine absurde répond true, alors absurde () s'appelle elle-même indéfiniment : elle ne termine pas. termine s'est trompée.
• Si termine absurde répond false, alors absurde () rend () immédiatement : elle termine. termine s'est encore trompée.

Dans les deux cas, termine donne une mauvaise réponse sur absurde. Une fonction termine qui répond toujours juste ne peut donc pas exister : le professeur s'est fait escroquer.

Conclusion sur la récursivité

Une bonne règle, enfin : ne pas essayer de suivre dans les moindres détails les appels récursifs pour comprendre ce que fait une fonction récursive. On vérifie le cas d'arrêt, on suppose que l'appel récursif fait ce qu'il doit, et on vérifie que le reste de la fonction en tire le bon résultat.