Vous ne pouvez pas comprendre la récursivité avant d'avoir compris la récursivité.
Anonyme
On parle de récursivité, lorsque, pour résoudre un
problème, on utilise des solutions d'instances «plus
petites» du même problème. Un algorithme récursif
«s'appelle lui-même» sur un problème plus petit.
Cette page présente quelques problèmes pouvant être résolus par une telle approche, et les liens avec la programmation dynamique.
Quelques grands classiques comme support à des explications sur la récursivité. Il est conseillé de regarder intégralement ces exemples avant de se pencher sur les suivants.
Il s'agit d'un jeu de réfexion dont le but est de déplacer
une tour constituée d'un empilement de $n$ pièces
cylindriques (de diamètres tous différents) percées d'un
trou du poteau de gauche au poteau de droite, en utilisant
un poteau intermédiaire, et en respectant les règles
suivantes:
on ne peut déplacer qu'une pièce à la fois. En
particulier, on ne pourra donc déplacer que la pièce
du haut d'une tour (qui a donc une structure de pile);
sur chaque poteau, les pièces doivent toujours
être empilées par diamètres décroissants.
Voici la configuration de départ pour un jeu à six pièces.
Ce problème peut typiquement être résolu par une approche récursive. Considérons
le problème avec $n\geq 2$ pièces, et supposons que nous
sachions résoudre le problème à $n-1$ pièces. On peut alors résoudre le problème à $n$ pièces de la façon suivante :
Déplacer $n-1$ pièces du premier poteau vers le poteau intermédiaire.
Déplacer la plus grand pièce du premier vers le dernier poteau.
Déplacer les $n-1$ pièces du poteau intermédiaire vers le dernier.
Et c'est (presque) tout : le problème à $n-1$ pièces
sera lui-même résolu en utilisant la solution du problème
à $n-2$ pièces, etc, ce sans avoir à écrire la moindre
boucle. Reste simplement à gérer le cas de base. Ici,
il s'agit de déplacer une seule pièce d'un poteau à
l'autre.
On obtient finalement l'algorithme suivant pour déplacer
$n$ pièces du poteau $a$ au poteau $b$.
Tours de HanoïHanoï($a ➤ b$, $n$)
Si $n = 1$, déplacer une pièce de $a$ vers $b$
Sinon, en notant $c$ le poteau différent de $a$ et $b$
appeler Hanoï($a ➤ c, n-1$)
déplacer une pièce de $a$ vers $b$
appeler Hanoï($c ➤ b, n-1$)
Hors cas de base, chaque appel de la fonction va générer deux nouveaux appels - ce qui peut être représenté sous forme d'un arbre des
appels comme ci-dessous. Cet arbre est une
représentation abstraite des appels récursifs.
Lors de l'exécution, la plupart des langages vont concrètement maintenir une pile d'exécution, qui contient des informations concernant les fonctions «actives» (arguments de la fonction, point du code où retourner à la fin de son exécution, etc.). Lorsqu'une fonction est appelée, ces informations sont empilées, et lorsque son exécution est terminée, elles sont dépilées.
Lors de l'exécution de l'algorithme récursif, les appels
stockés dans la pile correspondent à la branche reliant la
racine (le premier appel de fonction) à l'appel en cours
d'exécution.
Arbre des appels récursifs
Pile d'exécution
La complexité temporelle de l'algorithme est
la somme des complexités de chaque sommet de
l'arbre des appels. Ici, si l'on choisit comme
opération élémentaire le déplacement d'une
pièce et si l'on note $u_n$ le nombre de
déplacements de pièces utilisé par cet
algorithme pour résoudre le problème à $n$
pièces,
$\left\{\begin{array}{l} u_1=1\\\forall n\in\mathbb{N}^*,\ u_{n+1}=2u_n+1\end{array}\right.$.
Une récurrence facile montre alors que pour
tout $n\in\mathbb{N}^*$, $u_n=2^n-1=O(2^n)$.
Une autre façon de retrouver ce résultat
est de constater qu'il y a exactement un
déplacement par sommet de l'arbre. En comptant
le nombre de sommets ligne par ligne, on obtient
$\sum_{k=0}^{n-1}2^k=2^n-1$.
Indépendamment de la complexité spatiale
intrinsèque de l'algorithme, la pile nécessitera un
espace proportionnel à la longueur de la branche la
plus profonde de l'arbre, ici $O(n)$. Cela peut être un argument pour chercher un algorithme itératif utilisant moins de mémoire pour résoudre le problème.
Figures alphanumériques
Comparez les deux fonctions suivantes, en essayant
d'anticiper leur exécution et leur résultat.
Triangle 1Triangle1($n$)
Afficher $n$ «$\star$» sur une ligne.
Si $n>0$, appeler Triangle1($n-1$)
Triangle 2Triangle2($n$)
Si $n>0$, appeler Triangle2($n-1$)
Afficher $n$ «$\star$» sur une ligne.
La réponse ci-dessous.
Triangle 1
Arbre des appels récursifs
Pile d'exécution
Triangle 2
Arbre des appels récursifs
Pile d'exécution
Dans les deux cas, l'arbre des appels récursifs est
réduit à une branche. Le comportement de la pile
d'appels est simple : les appels vont être
empilés par ordre décroissant de $n$, puis dépilés. La seule différence est le moment où l'affichage est effectué.
Dans Triangle1, l'affichage est effectué avant d'empiler un nouvel appel. Les affichages successifs ont donc lieu lors de la «descente» dans l'arbre des appels, donc par $n$ décroissants.
Dans Triangle2, l'affichage est effectué après avoir empilé puis dépilé un nouvel appel. Les affichages successifs ont donc lieu lors de la «remontée» dans l'arbre des appels, donc par $n$ croissants.
À titre d'exercice, deviner le comportement des deux algorithmes suivants pour de petites valeurs de $n$, puis testez !
Figure 1Figure1($n$)
Afficher $n$ «$\star$» sur une ligne.
Si $n>0$, appeler Figure1($n-1$)
Afficher $n$ «$\star$» sur une ligne.
Figure 2Figure2($n$)
Si $n>0$, appeler Figure2($n-1$)
Afficher $n$ «$\star$» sur une ligne.
Si $n>0$, appeler Figure2($n-1$)
Figure 1
Figure 2
Triangle de Sierpiński
Il s'agit d'une figure fractale, obtenue à partir d'un
triangle équilatéral par le mécanisme suivant :
Relier les milieux des côtés, de façon à créer quatre zones triangulaires.
Enlever la zone du milieu.
Recommencer dans chacune des trois zones restantes - et poursuivre indéfiniment.
Nous pouvons facilement construire un algorithme récursif effectuant $n$ itérations de cette procédure.
Triangle de SierpińskiSierpiński($t, n$)
Découper le triangle t en quatre triangles comme indiqué ci-dessus.
Enlever le triangle central.
Si $n>1$, en notant $t_1$, $t_2$ et $t_3$ les triangles restants,
Appeler Sierpinski($t_1, n-1$)
Appeler Sierpinski($t_2, n-1$)
Appeler Sierpinski($t_3, n-1$)
L'application ci-dessous démontre l'exécution de cet algorithme pour $n=7$. Dans la figure représentant la pile d'exécution, les valeurs correspondent aux coordonnées du sommet supérieur du triangle sur lequel la fonction est appelée, et à sa hauteur.
Notons $u_n$ le nombre de suppressions de triangles
effectuées lorsqu'on appelle l'algorithme avec $n$
comme second argument. On a immédiatement la relation
$$\left\{\begin{array}{l} u_1=1\\\forall n\in\mathbb{N}^*,\ u_{n+1}=3u_n+1\end{array}\right..$$
On montre alors par récurrence que pour tout $n\in\mathbb{N}^*$, $u_n=\frac{3^n-1}{2}$.
Recherche dichotomique dans un tableau trié
Voici une implémentation récursive de recherche
dichotomique d'un élément dans un tableau trié
(contenant des éléments d'un type «ordonnable» :
nombres, chaînes, etc).
Recherche dichotomique récursiveRecherche($e, t, d, f$) //cherche l'élément e dans le tableau t, entre les indices d et f inclus (pour début et fin). Renvoie un indice où apparaît l'élément, faux si l'élément n'apparaît pas.
Si $f\lt d$, renvoyer faux
Sinon
Calculer la moyenne $m$ entre $d$ et $f$ (arrondie à l'entier inférieur)
Si $t[m] = e$, renvoyer $m$
Si $t[m] < e$, renvoyerRecherche($e, t, m+1, f$)//rechercher dans la moitié droite de l'intervalle
Si $t[m] > e$, renvoyerRecherche($e, t, d, m-1$)//rechercher dans la moitié gauche de l'intervalle
Dans l'application ci-dessous, la frise en gradient de
gris représente un tableau de 1000 entiers entre 0 et
$10^6$, classés par ordre croissants (chaque élément
est tiré selon une loi uniforme, et le niveau de gris
est fonction de sa valeur : blanc pour 0, noir
pour $10^6$). En passant la souris sur la frise, vous
lancez l'exécution de l'algorithme de dichotomie pour
chercher l'entier correspondant à la position de la
souris. Si vous déplacez la souris hors de la frise, l'algorithme recherche une valeur aléatoire qui n'est pas contenue dans le tableau.
Évaluons le nombre maximal d'appels récursifs
nécessaires en fonction du nombre d'éléments $n =
f-d+1$ dans le sous-tableau où l'on recherche $e$. Notons-le $u_n$. On obtient immédiatement les relations suivantes:
$$\left\{
\begin{array}{l}
u_0 = 1\\
\forall n\in\mathbb{N},\ u_{n}=u_{\lfloor n/2\rfloor}+1
\end{array}
\right.$$
On prouve que le nombre d'appel récursifs est $O(\log(n))$ - à comparer avec le $O(n)$ d'une recherche linéaire - soit en utilisant le Master Theorem, qui permet des calculs de complexités pour de nombreuses fonctions récursives, soit :
en prouvant par récurrence que pour tout $m\geq 0$, $u_{2^m}=m+1$,
puis que $(u_n)$ est croissante (par récurrence forte),
et enfin, en remarquant que $2^{\lfloor \log_2(n)\rfloor}\leq n\leq 2^{\lfloor \log_2(n)\rfloor+1}$, pour obtenir $\lfloor \log_2(n)\rfloor + 1\leq u_n\leq \lfloor \log_2(n)\rfloor +2$.
Une parenthèse sur la récursivité terminale
Nous sommes ici dans un cas particulier où chaque appel engendre au plus un appel
récursif, et où le résultat de la fonction appelée est
immédiatement renvoyé par la fonction
appelante. L'appel récursif est donc la dernière
fonction à être évaluée. On parle de récursivité teminale.
Il est facile de dérécursifier une telle
fonction - c'est-à-dire de la transformer en une
fonction purement itérative - ce qui permet de ne pas
avoir à payer le coût en espace de la pile d'appel. Certains langages effectuent automatiquement cette opération.
Voici une façon générale de procéder, pour une fonction de paramètre $p$, où :
$B$ est l'ensemble des cas de bases
$base(p)$ est la valeur à renvoyer si $p\in B$
$g(p)$ est le paramètre de l'unique appel récursif à effectuer si $p\not\in B$
Une fonction récursive terminalef($p$)
Si $p\in B$
renvoyer $base(p)$ //cas de base.
Sinon
renvoyer f$(g(p))$ //appel récursif.
La fonction dérécursifiéef($p$)
Tant que $p\notin B$
$p\leftarrow g(p)$
renvoyer $base(p)$
Voici la version dérécursifiée de l'algorithme de dichotomie.
Recherche dichotomique dérécursifiéeRecherche($e, t, d, f$) //cherche l'élément e dans le tableau t, entre les indices d et f inclus (pour début et fin). Renvoie un indice où apparaît l'élément, faux si l'élément n'apparaît pas.
Tant que $f\geq d$
Calculer la moyenne $m$ entre $d$ et $f$ (arrondie à l'entier inférieur)
Si $t[m] = e$, renvoyer $m$
Si $t[m] < e$, $(d, f)\leftarrow (m+1, f)$ //rechercher dans la moitié droite de l'intervalle
Si $t[m] > e$, $(d, f)\leftarrow (d, f-1)$ //rechercher dans la moitié gauche de l'intervalle
Renvoyer faux
Tri par partition-fusion : un exemple de stratégie diviser pour régner.
La stratégie diviser pour régner consiste, pour résoudre un problème donné :
à le découper en sous-problèmes
puis résoudre chacun de ces sous-problèmes récursivement
et enfin, à construire une solution au problème initial à l'aide des solutions des sous-problèmes.
Elle s'applique à de nombreux domaines, et nous la présentons ici sur le problème de tri de tableaux.
Tri par partition fusion Trier($t$ entre les indices $i$ et $j$)
Si $j-i=0$, ne rien faire //on doit trier 1 élément !
Sinon,
$m\leftarrow \lfloor \frac{i+j}{2}\rfloor$
Trier($t$ entre les indices $i$ et $m$)
Trier($t$ entre les indices $m+1$ et $j$)
fusionner les sous-tableaux triés dans les deux points précédents pour trier $t$ entre $i$ et $j$
La fusion peut être implémentée à partir de la fonction suivante ($t_1$ et $t_2$ étant remplacés par les sous-tableaux triés récursivement) - le résultat obtenu sera ensuite recopié dans $t$ entre les indices $i$ et $j$.
Fusion Fusion($t_1$, $t_2$)
Créer un tableau $t$ de longueur égale à la somme $n$ des longueurs de $t_1$ et $t_2$ (que l'on notera $n_1$ et $n_2$ dans la suite)
Initialiser trois compteurs $i$, $i_1$ et $i_2$ à 0
Tant que $i\lt n$
Si $i_2 = n_2$ ou $t_1[i_1] < t_2[i_2]$
$t[i]\leftarrow t_1[i_1]$
Incrémenter $i$ et $i_1$
Sinon
$t[i]\leftarrow t_2[i_2]$
Incrémenter $i$ et $i_2$
Évaluons le nombre maximal d'accès aux éléments du
tableaux nécessaires à son tri en fonction de son
nombre d'éléments $n$. Notons-le $u_n$. On obtient
immédiatement les relations suivantes:
$$\left\{ \begin{array}{l} u_1 = 0\\ u_{n}=u_{\lfloor n/2\rfloor}+u_{\lceil n/2\rceil}+O(n)
\end{array} \right.$$
($O(n)$ étant la complexité de la fusion).
D'après le Master Theorem,
le nombre d'accès est donc $O(n\log(n))$. On peut montrer qu'il
s'agit asymptotiquement d'une complexité optimale pour
un algorithme de tri basé sur une fonction de
comparaisons.
L'algorithme de tri standard utilisé par Python est une variante du tri par partition-fusion.
Suite de Fibonacci : un pas vers la programmation dynamique
Ou une mauvaise utilisation de la récursivité…
et un pas vers la programmation dynamique.
On souhaite écrire une fonction calculant le terme
d'indice $n$ de la suite de Fibonacci définie par
$\left\{\begin{array}{l}u_0=0\\u_1=1\\\forall
n\in\mathbb{N},\
u_{n+2}=u_{n+1}+u_n\end{array}\right.$. On peut
penser naïvement à l'algorithme récursif
suivant :
Fibonacci récursifFibonacci($n$)
Si $n=0$, renvoyer 0
Si $n=1$, renvoyer 1
Sinon, renvoyerFibonacci($n-1$)+Fibonacci($n-2$)
On montre (par récurrence double sur $n$) que le nombre d'appels récursifs pour
calculer $u_n$ est $2u_{n+1}-1$, et que le nombre d'additions effectuées est $u_{n+1}-1$. Ce qui est de
l'ordre de
$\left(\frac{1+\sqrt{5}}{2}\right)^{n+1}$. On a donc
une complexité exponentielle en temps (et linéaire en
espace). Le problème est que les mêmes valeurs sont
recalculées de nombreuses fois à plusieurs endroits
différents de l'arbre. On parle de chevauchement de sous-problèmes - et l'arbre des appels récursifs est avantageuseument remplacé par un graphe.
Un algorithme récursif naïf n'est donc pas adapté pour résoudre ce type de problème, qui relève du champ de la programmation dynamique. Selon Wikipedia «la
programmation dynamique consiste à résoudre un
problème en le décomposant en sous-problèmes, puis à
résoudre les sous-problèmes, des plus petits aux plus
grands en stockant les résultats intermédiaires».
La première solution est de modifier notre algorithme en lui ajoutant un processus de mémoïsation : les valeurs calculées vont être stockées dans un tableau, auquel on pourra se référer plutôt que de refaire des calculs inutiles.
Fibonacci «descendant» (récursif avec mémoïsation)Fibonacci($n$)
Initialiser un tableau $t$ de longueur $n+1$ à «$?$»
$t[0]\leftarrow 0$
$t[1]\leftarrow 1$
Fibonacci_auxiliaire($n$)
Si $t[n]$ n'est pas égal à «$?$», renvoyer $t[n]$
Sinon, $t[n]\leftarrow$ Fibonacci_auxiliaire($n-1$)+Fibonacci_auxiliaire($n-2$), et renvoyer $t[n]$
RenvoyerFibonacci_auxiliaire($n$)
Valeurs mémorisées
La complexité temporelle est désormais linéaire (en choisissant comme opération élémentaire l'addition, ou l'accès à un élément du tableau) - ainsi que la complexité spatiale.
L'algorithme précédent est une méthode descendante pour calculer les termes de la suite de Fibonacci : lorsqu'on appelle l'algorithme pour une valeur initiale $n$, les appels récursifs descendent vers $n-1$, $n-2$, etc.
On peut également coder ce calcul de façon itérative ascendante ou de bas en haut (car il est possible de déterminer très facilement un ordre pour le calcul des Fibonacci($n$) successifs : celui des $n$ croissants - ce qui est lié au fait qu'il est facile d'effectuer un tri topologique du graphe des appels récursifs).
Fibonacci «ascendant»Fibonacci($n$)
Initialiser un tableau $t$
de longueur $n+1$ à «$?$». $t[0]\leftarrow 0$,
et $t[1]\leftarrow 1$.
Pour $i$ variant de $2$ à $n$
$t[n]\leftarrow t[n-1]+t[n-2]$
renvoyer $t[n]$
La complexité temporelle est toujours linéaire - ainsi que la complexité spatiale.
Et voici une variante toujours ascendante plus économe en mémoire - basée sur le fait que le calcul d'un terme ne nécessite que les valeurs des deux termes précédents.
Fibonacci «ascendant»Fibonacci($n$)
$ad\leftarrow 1$ //avant dernier terme calculé
$d\leftarrow 1$ //dernier terme calculé
Pour $i$ variant de $2$ à $n$
$(d, ad)\leftarrow (d+ad, d)$
Renvoyer $d$
La complexité temporelle est toujours linéaire, et la complexité spatiale est désormais constante.
Cette dernière version est convertible en une version récursive (terminale) :
Fibonacci récursif, version 2Fibonacci($n$)
Fibonacci_auxiliaire($n, a, b$)
Si $n=0$ renvoyer $a$
Si $n=1$ renvoyer $b$
SinonrenvoyerFibonacci_auxiliaire($n-1, b, a+b$)
RenvoyerFibonacci_auxiliaire($n, 0, 1$)
Terminons avec un algorithme sans boucle ou récursion, s'exécutant en temps et espace constant (si l'on considère que c'est le cas pour les opérations mathématiques impliquées), au prix d'un peu de Mathématiques ! Les calculs étant effectués par des flottants, le résultat risque par contre de ne plus être exact pour $n$ «grand». Un test en Python sur une machine 64 bits donne un résultat qui n'est plus entier dès $n=4$, et dont la valeur entière la plus proche n'est pas la valeur correcte pour $n=71$.
Suivent d'autres exemples d'algorithmes récursifs. Pas de nouveauté conceptuelle (à part le backtracking, qui déborde du programme d'ITC), mais un panorama de problèmes qui peuvent être résolus par une stratégie récursive.
Exponentiation rapide
L'idée de l'exponentiation rapide est contenue dans la formule suivante, valable pour tout $x\in\mathbb{R}$ (ou à un groupe multiplicatif quelconque) et $n\in\mathbb{N}$ :
$$x^n=\left\{\begin{array}{l}1\text{ si }n=0\\(x^2)^{n/2}\text{ si }n\text{ est pair}\\x(x^2)^{(n-1)/2}\text{ si }n\text{ est impair} \end{array}\right.$$
d'où l'on déduit l'algorithme ci-dessous.
Exponentiation rapidePuissance($x, n$)
Si $n=0$, renvoyer 1
Si $n$ est pair, renvoyer Puissance($x^2, n/2$)
Si $n$ est impair, renvoyer $x\times$Puissance($x^2, (n-1)/2$)
L'application suivante montre le cas $x=2$.
Chaque appel récursif effectue au plus deux multiplications et une division. Une analyse similaire à celle de la recherche par dichotomie montre
que le nombre d'appels récursifs est $O(\log(n))$. Si
l'on suppose que les opérations arithmétiques
s'effectuent en temps constant, la complexité
temporelle de l'exponentiation rapide est
$O(\log(n))$, ce qui est une accélération très
importante par rapport au $O(n)$ de l'algorithme de
calcul de puissances naïf.
L'algorithme ci-dessus n'est pas récursif terminal à
cause du $x\times$ du cas où $n$ est impair, qui est
une opération effectuée après l'appel récursif.
On peut obtenir une fonction purement récursive à
l'aide d'un accumulateur $a$ (qui «stocke» en quelque sorte les produits par $x$), auquel on donnera la valeur $1$ au premier appel :
Exponentiation rapide récursive terminalePuissance_aux($x, n, a$)
Si $n=0$, renvoyer $a$
Si $n$ est pair, renvoyer Puissance_aux($x^2, n/2, a$)
Si $n$ est impair, renvoyer Puissance_aux($x^2, (n-1)/2, x\times a$)
Noter que la stratégie d'exponentiation rapide peut
être utilisée pour calculer des puissances de
matrices. Le produit matriciel naïf pour deux
matrices $n\times n$ étant en $O(n^3)$, il y a un
enjeu fort à faire moins de produits.
Sous-listes
On souhaite afficher toutes les sous-listes possibles d'une liste $l$, i.e. toutes les listes obtenues par la suppression d'un nombre quelconque d'éléments de $l$.
SousListes($l$, $a$) //affiche toutes les sous-listes de $l$ auxquelles on concatène la liste $a$ à la fin
Si $l$ est vide, afficher $a$
Sinon
noter $f$ l'élément de fin de la liste, et $d$ la liste privée de son dernier élément.
appeler SousListes($d$, $a$)//affichage des sous-listes ne contenant pas $f$
appeler SousListes($d$, $[f]+a$)//affichage des sous-listes contenant $f$
Il suffit alors d'exécuter cet algorithme avec $a=[]$
pour afficher toutes les sous-listes de $l$.
Notons $u_n$ le nombre total d'appels récursifs effectués
pour une liste de longueur $n$. On a
$$\left\{\begin{array}{l} u_0=1\\\forall n\in\mathbb{N},\ u_{n+1}=1+2u_n\end{array}\right.$$
et une récurrence facile permet d'obtenir $u_n=2^{n+1}-1$ pour tout $n\in\mathbb{N}$.
En supposant que l'affichage s'effectue en
$O(n)$, que l'extraction de fin de liste s'effectue en
(au plus) $O(n)$, et que la contatenation de $[f]$ et
de $a$ s'effectue en $O(|a|)$, le coût en temps d'un
appel (hors ces appels récursifs) est
$O(n)$. L'algorithme proposé a donc une complexité
$O(n2^n)$.
Permutations
On souhaite afficher toutes les permutations possibles d'un tableau. On peut pour cela s'appuyer sur un algorithme récursif affichant toutes les permutations qui laissent fixes les $k$ premiers éléments du tableau.
AffichePermutations($t, k$) //affiche toutes les permutations de $t$ (de longueur $n$) laissant fixes les $k$ premiers éléments
Si $k = n-1$, afficher $t$
Sinon, pour $i$ variant de $k$ à $n-1$
Permuter $t[k]$ et $t[i]$
Appeler AffichePermutations($t, k+1$)
Permuter $t[k]$ et $t[i]$
Il suffit alors d'exécuter cet algorithme avec $k=0$
pour afficher toutes les permutations de $t$.
Comptons le nombre de permutations effectuées pour un
tableau à $n$ éléments. Chaque appel récursif effectue un nombre constant (2) de permutations.
En comptant les sommets de l'arbre des appels
récursifs ligne par ligne, on constate que le nombre
d'appels récursifs est $u_n=\sum_{k=0}^{n-1}
\frac{n!}{(n-k)!}$ (ce que confirme une récurrence sur
$n$). Un peu de mathématiques donne $u_n=n!\sum_{k=1}^n\frac{1}{k!}\sim en!=O(n!)$. (Voir par exemple la page OEIS de cette suite). On ne peut guère espérer faire mieux asymptotiquement pour engendrer les $n!$ permutations du tableau…
Génération de labyrinthe par parcours en profondeur
On souhaite générer un labyrinthe dans une grille régulière. Pour cela, on peut effectuer un parcours en profondeur des cases de la grille, en enlevant au fur et à mesure chaque mur séparant deux cases voisines dans le parcours.
Parcours($i, j$)
Marquer la case $(i,j)$ comme explorée
Tant que $(i,j)$ a une case voisine $c$ non explorée
Enlever le mur entre $(i,j)$ et $c$
AppelerParcours($c$)
On exécute alors cet algorithme en partant par exemple
de $(0,0)$ pour obtenir un labyrinthe - où chaque case est reliée toute autre par exactement un chemin sans cycle (le labyrinthe obtenu ayant une structure d'arbre). Le parcours en profondeur tend à trouver de très longs chemins. Il existe de nombreuses autres méthodes pour engendrer des labyrinthes, certaines donnant des résultats plus intéressants et équilibrés.
La complexité de cet algorithme est linéaire en le nombre de cases de la grille.
Génération de labyrinthe par diviser pour régner
Une autre stratégie pour générer un labyrinthe, utilisant cette
fois-ci une stratégie diviser pour régner. L'idée est de séparer la grille en deux sous-grilles rectangulaires (pas nécessairement de même taille afin de ne pas créer des labyrinthes trop réguliers), d'appeler récursivement l'algorithme sur ces sous-grilles, puis d'ouvrir un mur aléatoirement pour relier les deux sous-labyrinthes.
Labyrinthe($i, j, di, dj$) //générère un labyrinthe de dimension $(di, dj)$ à partir de la case $(i, j)$ en haut à gauche.
Si $di=1$ ou $dj=1$, enlever tous les murs reliant les cases situées sur la ligne droite entre $(i,j)$ et $(i+di-1, j+dj-1)$.
Sinon
Si $di>=dj$, tirer au hasard $c$ entre $1$ et $di-1$, puis appeler Labyrinthe($i, j, c, dj$) et Labyrinthe($i+c, j, di-c, dj$).
Sinon $di>=dj$, tirer au hasard $c$ entre $1$ et $dj-1$puis appeler Labyrinthe($i, j, di, c$) et Labyrinthe($i, j+c, di, dj-c$).
Enlever un mur aléatoirement entre les deux sous-labyrinthes crées
Pavages
On considère ici une grille carrée constituées de
$2^n\times 2^n$ cases. L'une des cases est «enlevée»,
et l'on souhaite paver l'ensemble des cases restantes (appelées cases vides dans la suite)
à l'aide de pièces en forme de «L» couvrant trois
cases.
Il est conseillé de commencer par prouver qu'un tel
pavage est possible en prenant une feuille et un
crayon pour comprendre l'algorithme ci-dessous.
Pavage($n$)
Si $n = 1$, recouvrir les trois cases vides à l'aide d'une pièce
Sinon,
Découper la grille en quatre quadrants de taille $2^{n-1}\times 2^{n-1}$
Placer une pièce à cheval sur les trois quadrants ne contenant que des cases vides
Paver récursivement les quatre quadrants.
Dans la pile des appels récursifs, sont indiquées
les coordonnées de la case située en haut à gauche du carré à paver
le côté de ce carré.
Pour compter le nombre d'appels récursifs nécessaire à
l'obtention du pavage, il est ici inutile de
travailler sur l'arbre des appels récursifs : il
suffit de constater que chaque appel récursif place
exactement une pièce, et que le nombre total de pièces
à placer est $\frac{(2^{n})^2-1}{3}$.
Tri rapide (diviser pour régner)
Le tri rapide consiste à choisir arbitrairement un élément dans le tableau (appelé pivot),
et placer les autres éléments par rapport à ce pivot
(les plus petits à gauche, les plus grands à droite),
puis à trier les parties du tableaux situées à gauche
et à droite du pivot.
Tri rapide Trier($t$ entre les indices $i$ et $j$)
Si $j-i\leq 1$, quitter sans rien faire //le sous-tableau à trier est de longueur 0 ou 1.
$pivot$ $\leftarrow$ $i$ //on pourrait choisir le pivot aléatoirement entre $i$ et $j$
$k\leftarrow$ Partitionner($t$, $i$, $j$, $pivot$) //réorganiser les éléments de $t$ entre les indices $i$ et $j$, de sorte que les éléments inférieurs à la valeur du pivot soient au début, les éléments supérieurs à la fin. La valeur renvoyée est le nouvel indice du pivot.
Trier($t$ entre les indices $i$ et $k-1$)
Trier($t$ entre les indices $k+1$ et $j$)
Le partitionnement peut être implémenté de la façon suivante.
$l \leftarrow i-1$ //indice maximum des éléments inférieurs à la valeur du pivot
Pour $k$ variant de $i$ à $j-1$
Si $t[k]\le valeur\_pivot$
$l \leftarrow l+1$
$t[l]\leftrightarrow t[k]$
$t[l+1]\leftrightarrow t[j]$//remise en place du pivot
renvoyer $l+1$
Tester différentes initialisations pour observer les
variations dans l'arbre des appels récursifs, et le nombre de comparaisons d'éléments du tableaux nécessaires à l'exécution. Dans la situation la plus défavorable, où le tableau est déjà trié, on montre facilement que l'algorithme s'exécute en temps $O(n^2)$ - $n$ étant la longueur du tableau.
Une analyse de l'algorithme montre que, lorsque toutes les permutations possibles des entrées sont équiprobables (ou si l'on choisit le pivot aléatoirement entre $i$ et $j$), la complexité moyenne de l'algorithme est $O(n\log(n))$.
Rendu de Monnaie (diviser pour régner)
On se donne ici un système de pièces,
c'est-à-dire un ensemble d'entiers strictement
positifs, par exemple $\{1,\ 2,\ 5\}$.
Étant donné un entier $s$ (correspondant à une somme d'argent), on se demande quelles sont les façons d'atteindre exactement cette somme à l'aide de pièces du système. Une même pièce peut être choisie plusieurs fois, et l'ordre des pièces n'a pas d'importance.
On peut utiliser la stratégie récursive suivante pour y parvenir - $s$ étant la somme à atteindre, et $l$ la liste des pièces déjà utilisées, classée par valeurs décroissantes.
Rendu de pièces Rendu($s$, $l$)
Si $s=0$, afficher $l$.
Sinon,pour
chaque pièce $p$ du système de pièces, si $p\leq s$ et $p$ n'est pas plus grande que la dernière valeur de $l$
Rendu($s-p$, $l+[p]$)
On appelle alors cet algorithme en partant de la liste $l$ vide.
La contrainte «$p$ n'est pas plus grande que la dernière valeur de $l$» implique que les pièces de la liste seront toujours classées par valeurs décroissantes - empêchant une même solution d'être atteinte plusieurs fois.
Un problème associé classique est de déterminer le
nombre minimal de pièces permettant d'atteindre $s$ (ce nombre correspond à la longueur de la plus courte branche atteignant la valeur 0 dans l'arbre des appels récursifs).
Pour certains systèmes de pièces, ce problème peut être très facilement résolu par l'algorithme glouton suivant, qui consiste à toujours choisir la pièce de plus grande valeur inférieure à la somme à rendre :
Rendu de pièce glouton RenduGlouton($s$, $l$)
Si $s=0$, afficher $l$.
Sinon
$p\leftarrow$ la plus grande pièce telle que $p\leq s$
RenduGlouton($s-p$, $l+[p]$)
Un système de pièces pour lequel l'algorithme glouton renvoie toujours la solution optimale est dit canonique. On
peut montrer que $\{1, 2, 5\}$ est canonique, mais pas
$\{1, 3, 4\}$ (pour $s=6$, l'algorithme glouton
renvoie $4+1+1$, ce qui n'est pas optimal, car
$3+3=6$). Les systèmes de monnaies réels vérifient généralement cette propriété !
Il s'agit dans le cas général d'un problème NP-complet (en particulier, on pense qu'il n'existe pas d'algorithme de complexité polynomiale en $n$ permettant de le résoudre).
GhostBusters
Egon Spengler : Don't cross the streams. Peter Venkman : Why ? Egon Spengler : It would be bad. Peter Venkman : I'm fuzzy on the whole good/bad thing. What do you mean, "bad" ? Egon Spengler : Try to imagine all life as you know it stopping instantaneously, and every molecule in your body exploding at the speed of light.
On se donne deux ensembles $F$ et $C$ de $n$ points dans le plan. Le premier est un ensemble de fantômes, le second de chasseurs de fantômes.
Tous les chasseurs doivent simultanément tirer sur exactement un fantôme à l'aide de leur canon à protons sans jamais que deux rayons se croisent. On
souhaite donc écrire un algorithme permettant de
relier les points de $C$ aux points de $F$ par des
segments, sans que jamais deux segments ne s'intersectent.
Dans la suite, on suppose les points en position générale,
en particulier qu'il n'y a pas trois points alignés dans $F\cup C$.
Ghost($F$, $C$)
Si $F$ et $C$ sont vides, ne rien faire.
Sinon, si $F$ et $C$ contiennent un unique élément chacun, relier ces éléments
Sinon
$b\leftarrow $ un fantôme ou chasseur d'ordonnée minimale parmi tous les fantômes ou chasseurs
trouver par balayage (cf ci-dessous) un chasseur ou fantôme $b'$ de sorte que la droite reliant $b$ et $b'$ sépare le plan en deux parties contenant chacune autant de fantôme que de chasseurs. On note $F_g$ et $C_g$ l'ensemble des fantômes et chasseurs situés d'un côté de cette ligne, et $F_d$ et $C_d$ ceux qui sont situés de l'autre.
appeler Ghost($F_g$, $C_g$)
appeler Ghost($F_d$, $C_d$)
Le balayage est illustré par la figure ci-contre.
Trouver le point $p$ le plus bas de $F\cup C$
Classer les autres points $p'$ par angle entre $(Ox)$ et $(pp')$ croissants
Balayer les points $p'$ par ordre croissant pour déterminer les lignes de séparation possibles
Parmi les lignes possibles, en choisir une qui sépare «le mieux possible» les points
Distance d'édition
On appelle distance d'édition ou distance de Levenshtein entre deux chaînes de caractères $s_1$ et $s_2$ le nombre minimal d'opérations élémentaires permettant de transformer $s_1$ en $s_2$, ou l'on entend par opération élémentaire :
la substitution d'un caratère par un autre,
l'insertion d'un caractère,
la suppression d'un caractère.
Cette distance sera notée $\operatorname{lev}(s_1,s_2)$ dans la suite.
Quelques exemples.
Pour tout chaîne $s$, $\operatorname{lev}(s, s)=0$ - aucune opération n'est nécessaire pour transformer une chaîne en elle même !
$\operatorname{lev}('lopin',\ 'lapin')=1$ - on peut passer de 'lopin' à 'lapin' en substituant le 'o' par un 'a' (1 opération), et il n'est pas possible de faire mieux.
$\operatorname{lev}('ACTGGT',\ 'ACGGTA')=2$ - on peut passer de la première chaîne à la seconde par suppression du premier T, et insertion d'un A à la fin, et on vérifie qu'il n'est pas possible de faire mieux.
Nous utilisons dans la suite des notations pythonesques :
$'\:'$ pour la chaîne vide
$len(s_1)$ pour la longueur de $s_1$
$s_1[0]$ pour le premier caractère de $s_1$
$s_1[1:]$ pour la chaîne privée de son premier caractère
La distance d'édition vérifie la formule suivante, qui va permettre de la calculer de façon récursive :
$$\operatorname{lev}(s_1,s_2)=\left\{\begin{array}{l}
len(s_1)\mathbf{\text{ si }}s_2 = '\:'\ \ \ \ \ (1)\\
len(s_2)\mathbf{\text{ si }}s_1 = '\:'\ \ \ \ \ (2)\\
\operatorname{lev}(s_1[1:], s_2[1:])\mathbf{\text{ si }}s_1[0] = s_2[0]\ \ \ \ \ (3)\\
1 + \min(\operatorname{lev}(s_1[1:], s_2),\ \operatorname{lev}(s_1, s_2[1:]),\ \operatorname{lev}(s_1[1:], s_2[1:]))\mathbf{\text{ sinon }}\ \ \ \ \ (4)
\end{array}\right.$$
(1) : transformer $s_1$ en la chaîne vide nécessite $len(s_1)$ suppressions.
(2) : transformer la chaîne vide en $s_2$ nécessite $len(s_2)$ insertions.
(3) : si les premiers caractères de $s_1$ et $s_2$ correspondent, leur distance d'édition ne change pas si on les supprime.
(4) : si les premiers caractères différent, c'est qu'il y a eu soit une suppression, soit une insertion, soit une substitution (correspondant aux trois arguments du min), et par conséquent un coût de $+1$ à payer.
L'algorithme récursif se déduit immédiatement de cette
formule. Il est illustré ci-dessous.
On constate en regardant l'arbre que des appels
récursifs qu'il y a de nombreux chevauchements de sous-problèmes (la fonction est appelée plusieurs fois avec les mêmes paramètres). On peut pour y remédier utiliser une
stratégie descendante avec mémoïsation (cf la section sur la suite de Fibonacci).
Pour cela, on va utiliser un tableau de taille $(len(s_1)+1)(len(s_2)+1)$ dont l'élément d'indices $(i, j)$ contient la valeur de $\operatorname{lev}(s_1[i:], s_2[j:])$ si celle-ci a déjà été calculée.
Chaque élément intérieur du tableau mémoïsé ne dépend
que des éléments situés à droite, en dessous, et en
diagonale en dessous à droite. Il est donc possible de
résoudre le problème par un algorithme itératif
ascendant.
Il est possible d'optimiser cet algorithme en ne
conservant en mémoire que la dernière colonne
entièrement calculée et celle qui est en train de
l'être au lieu du tableau tout entier. Conserver
l'intégralité du tableau peut cependant permettre de
«remonter le chemin» menant à la distance d'édition,
i.e. de trouver des opérations élémentaires expliquant
la valeur optimale atteinte.
Ces idées sont à la base de l'algorithme de Wagner et
Fisher pour l'alignement de séquences d'ADN, ou de méthodes de déformation temporelle dynamique utilisées en reconnaissance vocale.
Perles de Dijkstra (backtracking)
La technique du backtracking ou retour sur trace,
consiste en l'exploration en profondeur de l'espace
des configurations d'un problème donné, jusqu'à
trouver une configuration solution au
problème. Contrairement à un parcours en profondeur,
l'ensemble des configurations explorées n'est pas
mémorisée. Lorsque un «cul-de-sac» dans l'espace des
configurations est atteint, on revient en arrière
(«retour sur trace») pour chercher un autre chemin
vers une solution.
Cette technique se prête bien à une implémentation récursive.
Les perles
de Dijkstra sont un exemple classique de
problème pouvant être traité de cette façon. On
dispose de perles de trois couleurs :
aubergine (0), incarnat (1) et prasin (2), et l'on
souhaite mettre sur un fil $n$ perles de façon à
ce qu'il n'y ait aucun facteur carré,
c'est-à-dire deux séquences identiques qui se
suivent.
Par exemple 01120 n'est
pas une séquence valide (à cause des deux 1 successifs), 010210220 non plus (à
cause des deux 102
successifs), mais 01020120 oui.
L'algorithme ci-dessous permet d'obtenir une séquence
valide de longueur $n$. Pour cela, on ajoute
successivement des perles ne faisant pas apparaître de
facteurs carrés. En cas d'impossibilité, le dépilement
des appels fera revenir en arrière et essayer une
nouvelle possibilité.
Perles de Dijkstra Perles($s$, $n$)//$s$ désigne la séquence courante (initialement $[0]$), et $n$ le nombre de perles à ajouter pour atteindre la longueur voulue.
Notons $c_1$ et $s_2$ les couleurs différentes de celle de la dernière perle de $s$.
Si $s+[c_1]$ n'a pas de facteur carré et que Perles($s+[c_1]$, $n-1$) renvoie un succès, renvoyer un succès et la séquence obtenue.
Sinon, si $s+[c_2]$ n'a pas de facteur carré et que Perles($s+[c_2]$, $n-1$) renvoie un succès, renvoyer un succès et la séquence obtenue.
Sinon, renvoyer un échec.
On appelle alors cet algorithme en partant de la liste $l=[0]$.
Ce problème a par ailleurs une jolie solution théorique basée sur la suite de Thue-Morse.
Problèmes des $n$ dames (backtracking)
Le problème des $n$ dames consiste à placer $n$ dames sur un échiquier de taille $n\times n$, de façons à ce qu'aucune dame ne puisse en prendre une autre (les dames se déplaçant en ligne, colonne, ou diagonale).
Ce problème peut être abordé de nombreuses façons, mais
illustre de façon intéressante le backtracking.
On remarque que dans une solution, il y a exactement
une dame sur chaque colonne. On commence par placer
une dame sur la première colonne le plus haut
possible, puis une dame sur la deuxième le plus haut
possible qui ne puisse pas prendre la première, puis
une dame sur la troisième le plus haut possible qui ne
puisse prendre aucune des deux premières… On
poursuit ainsi colonne par colonne, et en cas
d'impossibilité, on revient en arrière pour déplacer
vers le bas la dernière dame placée. En cas de
blocage, on revient à l'avant-dernière, etc. Ce qui s'implémente facilement de façon récursive.
$n$ Dames Dames($positions$, $n$)//$positions$ désigne la liste des indices de lignes des dames déjà placées (initialement $[]$), et $n$ le nombre total de dames que l'on veut placer.
$i\leftarrow $ la longueur de $positions$ //la colonne sur laquelle on doit essayer de placer la prochaine dame
Si $i == n$, renvoyer un succès et $positions$ //on a placé les $n$ dames
Sinonpour chaque indice de ligne $j$ tel que placer une nouvelle dame en $(i,j)$ n'enfreigne pas la règle
appeler Dame($positions+[j]$, $n$)
Si l'appel est un succès, renvoyer le résultat de cet appel
Renvoyer un échec
On appelle alors cet algorithme en partant de la liste $l=[0]$.
Quelques liens vers d'autres algorithmes récursifs
L'algorithme de Karatsuba permet
de multiplier des nombres à $n$ chiffres ou des
polynômes de degré $n$ en temps $O(n^{\log(3)})$,
améliorant l'algorithme naïf en
$O(n^2)$. L'idée générale est de découper les entiers en deux moitiés (chiffres de poids fort/chiffres de poids faibles), puis, au lieu de faire naïvement 4 multiplications récursivement d'utiliser une astuce de calcul permettant de n'en faire que 3. ($\star$)
L'algorithme de Strassen utilise une stratégie «diviser pour régner» pour effectuer le produit de deux matrices de taille $n\times n$ avec une meilleure complexité que l'algorithme naïf en $O(n^3)$. L'idée est similaire à celle de Karatsuba : on découpe les matrices en 4 blocs, et une astuce permet de ne faire que 7 produits de blocs au lieu des 8 de la méthode naïve. ($\star$)
L'algorithme Quickselect permet de trouver en temps $O(n)$ en moyenne le $k$ème plus petit élément d'un tableau à $n$ éléments. L'algorithme «médiane des médianes» en est une adaptation, pour calculer la médiane d'un tableau en temps $O(n)$ au pire. ($\star\star$)