4.2 Récursivité : exemples classiques
Exercice 4.2 --- Calcul récursif de la factorielle.
Implanter le calcul récursif de la factorielle.
Exercice 4.3 --- Suite de Fibonacci.
La suite de Fibonacci est définie de manière récursive par la
relation :
un = un-1 + un-2.
Cette définition doit être complétée par une condition d'arrêt.
Dans notre cas, si n est égal à 0 ou 1 alors :
u0=u1=1.
Par curiosité, on peut tracer les calculs. Ainsi, si on veut
calculer u4 et que l'on suppose que le premier terme de la
somme est calculé en premier, on est confronté à la suite de
calculs :
| Fib(4) |
= |
|
|
|
Fib(3) |
|
+ |
|
Fib(2) |
| |
= |
|
Fib(2) |
|
+ |
Fib(1) |
+ |
|
Fib(2) |
| |
= |
Fib(1) |
+ |
Fib(1) |
+ |
Fib(1) |
+ |
|
Fib(2) |
| |
= |
1 |
+ |
Fib(1) |
+ |
Fib(1) |
+ |
|
Fib(2) |
| |
= |
1 |
+ |
1 |
+ |
Fib(1) |
+ |
|
Fib(2) |
| |
= |
|
2 |
|
+ |
Fib(1) |
+ |
|
Fib(2) |
| |
= |
|
2 |
|
+ |
1 |
+ |
|
Fib(2) |
| |
= |
|
|
|
3 |
|
+ |
|
Fib(2) |
| |
= |
|
|
|
3 |
|
+ |
Fib(1) |
+ |
Fib(1) |
| |
= |
|
|
|
3 |
|
+ |
1 |
+ |
Fib(1) |
| |
= |
|
|
|
3 |
|
+ |
1 |
+ |
1 |
| |
= |
|
|
|
3 |
|
+ |
|
2 |
| |
= |
|
|
|
5 |
Construire un programme qui calcul récursivement le nième
terme de la suite de Fibonacci.
Remarque.
Pour mémoire, comptons le nombre d'appel récursifs an pour
cette fonction. Par définition, on a :
a0=a1=1 et an=1+an-1+an-2
pour n>1.
Par changement de variable bn=an+1, on en déduit que :
b0=b1=2 et bn=bn-1+bn-2
pour n>1.
On a donc bn=2Fibn et ainsi, an=2Fibn-1. Or
si f désigne le nombre d'or ((5)1/2+1)/2, le
terme Fibn de la suite de Fibonacci est l'entier le plus proche
de fn/(5)1/2. Le nombre d'appels récursifs est donc
exponentiel en n. Comparez ce nombre avec le nombre d'itérations
nécessaires pour calculer la suite de Fibonacci.
Ce comportement n'est pas la règle en matière de récursivité.
L'écriture récursive tout en étant synthétique peut se
révéler efficace.
Exercice 4.4 --- La fonction 91 de MacCarthy.
Pour tout entier n, MacCarthy a défini la fonction
récursive f suivante :
| f(n) =
|
| n - 10 si n> 100 |
| f(f(n+11)) sinon. |
|
Attention.
Il n'est pas évident en C qu'une fonction définie par
récursivité imbriquée soit correcte. Prenons comme exemple, la
fonction de Morris :
int Morris(int a, int b){
if (a == 0)
return 1 ;
else
return Morris(a-1,Morris(a,b)) ;
}
Que vaut Morris(1,0) ? Par construction, on a
Morris(1,0)=Morris(0,Morris(1,0)). Puisqu'en C le passage
d'argument se fait par valeur, cette définition récursive ne
termine pas.
Exercice 4.5 --- Implantation récursive de l'algorithme d'Euclide.
Implanter une procédure récursive permettant le calcul du plus
grand commun dénominateur (cf. 3.1.2).
Déterminer le nombre d'appels récursifs nécessaire au calcul
du pgcd de a et b en fonction de a.
Exercice 4.6 --- le jeu des Tours de Hanoï.
En 1883, Édouard Lucas (1842--91) publie sous le nom de Claus de
Siam professeur au collège de Li-Sou-Tsian --- anagramme de Lucas
d'Amiens professeur à Saint-Louis --- le jeu des Tours de
Hanoï. Le jeu est constitué de trois piquets verticaux
--- 1, 2 et 3 --- et de disques superposés de tailles
strictement décroissantes enfilés autour du piquet 3 ; ces
disques forment les fameuses tours.
Figure 4.1 : L'état initial du jeu des Tours de Hanoï pour n=4
Il faut déplacer l'ensemble des disques pour que ceux-ci se
retrouvent enfilés autour du piquet 3 en respectant les règles
suivantes :
-
les disques sont déplacés un par un ;
- un disque ne doit pas se retrouver au-dessus d'un disque plus
petit.
Lucas a montré que le problème est toujours résoluble et que
pour une tour de n étages, il faut au minimum 2n-1 coups
pour déplacer la tour. La légende veut que les bonzes d'Hanoï
passaient leur vie à résoudre ce problème pour n=127, ce qui
leur permettait d'attendre l'écroulement du temple de Brahma et donc
la fin du monde. Pour mémoire, 2127-1 est un nombre de
Mersenne dont Lucas a démontré la primalité.
Raisonnement par récurrence
L'idée de la récursivité telle que nous l'employons aujourd'hui
est attribuable à Stephan C. Kleene (1909--94) notion offre une
solution élégante au problème des Tours de Hanoï.
Principe.
Supposons notre problème résolu pour n-1 disques i.e. que
l'on sache transférer n-1 disques depuis le piquet i jusqu'au
piquet j en respectant les règles du jeu. Il existe alors une
solution simple pour transférer n disques dans les mêmes
conditions :
-
on amène les n-1 disques du haut du piquet i sur le
troisième piquet --- représenté par 6-(i+j) ;
- on prend le dernier disque du piquet i et on le met seul
en j ;
- on ramène les n-1 disques de 6-(i+j) en j.
Implantation.
Construire une fonction Hanoi.c qui permet d'afficher les
mouvements élémentaires à accomplir pour déplacer n disques
du piquet i au piquet j (une procédure principale est fournie).
Utiliser cette fonction dans un programme C qui demande à
l'utilisateur le nombre de disque à placer sur le premier piquet et
qui affiche une solution du jeu.
Exercice 4.7 --- Le problème des reines.
Le problème des reines consiste à placer n reines sur un
échiquier de taille n× n de telle sorte qu'aucune reine
ne soit en prise : il ne faut donc pas plus d'une reine par ligne,
par colonne et par diagonale.
Voici un exemple de solution pour n=8 :
On peut trouver les solutions du problème des reines en explorant
récursivement l'espace des configurations possibles. Le but de
l'exercice sera de compter le nombre de solutions du problème des
reines pour un entier n donné.
Ainsi, pour n=1, il y a une seule configuration, pour n=2,
il n'y en a pas, etc.
L'algorithme nécessite trois tableaux de booléens représentant
les contraintes engendré par le placement des reines. Il y a un tableau qui indique
-
pour chaque ligne si elle est déjà occupée par une reine ;
- pour chaque diagonale ``descendante'' si elle est déjà occupée par une reine ;
- pour chaque diagonale ``montante'' si elle est déjà occupée par une reine.
Pour la mise au point du programme, on pourra ajouter un tableau
pour stocker la solution en cours de construction.
L'algorithme consiste à placer une reine dans chaque colonne et
à mettre à jours les tableaux ci-dessus. Il n'y a qu'une
fonction récursive à écrire. Elle prend en argument le
numéro i de la colonne à explorer et les trois tableaux. Elle
retourne le nombre de solutions possibles avec les reines dèjà
placées dans les colonnes 0 à i-1.
Pour tout commentaire : Alexandre Sedoglavic.