retour
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. Un panorama d'autres algorithmes récursifs

Tours de Hanoï

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: 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 : 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$)
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


Figures alphanumériques

Comparez les deux fonctions suivantes, en essayant d'anticiper leur exécution et leur résultat.
Triangle 1 Triangle1($n$)
Triangle 2 Triangle2($n$)
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é.
À titre d'exercice, deviner le comportement des deux algorithmes suivants pour de petites valeurs de $n$, puis testez !
Figure 1 Figure1($n$)
Figure 2 Figure2($n$)


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 : Nous pouvons facilement construire un algorithme récursif effectuant $n$ itérations de cette procédure.
Triangle de Sierpiński Sierpiński($t, n$)
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écursive Recherche($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.

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  :

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ù :
Une fonction récursive terminale f($p$)
La fonction dérécursifiée f($p$)

Voici la version dérécursifiée de l'algorithme de dichotomie.
Recherche dichotomique dérécursifiée Recherche($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.

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é : 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$)
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$)


É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écursif Fibonacci($n$)


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$)



       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$)

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$)

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 2 Fibonacci($n$)



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$.
Fibonacci sans boucle Fibonacci($n$)


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 rapide Puissance($x, n$)

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 terminale Puissance_aux($x, n, a$)
Puissance($x,n$)



On peut alors dérécursifier pour obtenir une fonction itérative selon la méthode expliquée dans la section sur la recherche dichotomique.
Exponentiation rapide itérative Puissance($x, n$)
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
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
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…

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$)

Dans la pile des appels récursifs, sont indiquées

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$)
Le partitionnement peut être implémenté de la façon suivante.
Partitionnement
Partitionner($t$, $i$, $j$, $pivot$)



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$)
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$)
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$)



Le balayage est illustré par la figure ci-contre.





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 : Cette distance sera notée $\operatorname{lev}(s_1,s_2)$ dans la suite.
Quelques exemples. Nous utilisons dans la suite des notations pythonesques : 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.$$
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.
Distance d'édition (algorithme ascendant) Distance($s_1$, $s_2$)

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.
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.
On appelle alors cet algorithme en partant de la liste $l=[0]$.




Quelques liens vers d'autres algorithmes récursifs


Références