Cours Algorithme : La récursivité et Les Structures Recursives et La Programmation Dynamique avec des Exemples
- La Récursivité.
- Les Structures Récursives (Liste, Arbre...)
- La Programmation Dynamique.
1 Récursivité
1.1 Idée
une fonction peut s’appeler elle-même exactement comme un appel d'une autre fonction. Dès l'appel récursif achevé l'exécution du programme continue (et sans effet sur les variables et paramètres de l'appel initial).
Cette méthode est valable pour les fonctions et procédures (fonctions void).
On parle aussi de récursivité mutuelle lorsque deux ou plusieurs fonctions s'appellent entre elles (donc appel avant déclaration pour quelques unes).
1.2 Exemples favoris
1.2.1 Calcul de factorielle
Fonction fact(n) : entier
Début
Si (n=0) retourner (1)
Sinon retourner (n*fact(n-1))
Fin
1.2.2 Fibonacci
Fonction Fb(n) : entier
Début
Si (n£2) retourner 1
Sinon retourner (Fb(n-1)+Fb(n-2))
Fin
1.2.3 Remarques
La fonction récursive est une méthode bizarre de calculer une factorielle. Une boucle simple suffit. La fonction récursive est une très mauvaise méthode de calculer une suite de Fibonacci car le temps de calcul est exponentiel!
Donc, ne pas oublier qu’une méthode récursive est plus élégante et claire… mais il faut aussi considérer le temps de calcul, l’efficacité.
1.3 Meilleurs exemples
1.3.1 Calcul de xn
Fonction Puissance (x, n) : réel
Début
Selon que :
N=1 : retourner x
N%2=0 : retourner carrée(puissance(x,n/2))
Défaut : retourner x*carrée(puissance(x,n/2))
Fin
Remarque : on saute de xi à x2i dans une seule multiplication, ce qui est plus difficile à gérer avec une boucle. Il s’agit donc d’un bon exemple d’utilisation de fonction récursive.
1.3.2 Tour de Hanoi
1.3.2.1 Rappel du principe
Déplacer une tour de n disques de taille différente d'une colonne à une autre en utilisant une seule colonne auxiliaire, selon la règle qu'on ne peut déplacer qu'un disque à la fois et chaque colonne a toujours ses disques en ordre décroissante de taille.
1.3.2.2 Algorithme
Procédure Hanoi(n {nombre de disques}, a, b, c {tours})
Début
Si n=0 alors exit
Hanoi(n-1,a, c, b)
Afficher(a vers b)
Hanoi (n-1, c, b, a)
Fin
L’appel initial peut être : Hanoi(64, 1, 2, 3)
1.3.3 Autres exemples
- Affichage en (disons) binaire : une boucle simple affiche les chiffres dans l'ordre inversé
- Boucles imbriquées de profondeur inconnue
- Algorithmes « diviser pour régner »
1.4 Paramètres et variables locales
Les paramètres et les variables déclarées localement dans une fonction (si elle est récursive ou non) sont créés au moment de l'appel/activation de la fonction et continuent à exister jusqu’à la sortie finale de l'appel.
Ils sont inaccessibles et immuables pendant d'autres appels imbriqués (sauf utilisation de pointeurs...) Donc, quand une fonction s'appelle récursivement, à un moment de l'exécution du programme, il existe un nombre indéfini d'occurrences de ses paramètres et variables, mais, en général une seule occurrence accessible. Il y a possibilité d'échec parce que l'espace mémoire ne suffit pas pour toutes ces variables (segmentation fault en C).
1.5 Exemples utilisant des tableaux
1.5.1 Listes multiplicatives
Procédure Suites(n, m, T) :
Début
Afficher (n, T[n], T[n-1], …,T[1])
T[m+1]<- n
Pour i de 1 à n/2 faire :
Si n%i=0 Suites(i, m+1, T)
Fin
1.5.2 Recherche d’un parcours de l’échiquier par un cavalier (et revenir au début)
Procédure Cavalier (i, j, n, T) {i, j : position – T tableau à double entrée – n : nombre de coups/cases parcourues}
Début
Selon que :
i£0 ou j £0 ou i>8 ou j>8 : exit
i=1 et j=1 et n=65 afficher FIN
cas T[i,j]>0 exit {Si =0 : alors la case n’a pas encore été parcourue}
Défaut : T[i, j]<-n
Cavalier (i-2, j-1, n+1, T)
…
Fin
2 Structures récursives
2.1 Définition
On appelle structure récursive une structure qui contient un (des) pointeur(s) cers une structure de même type.
2.1.1 Exemple 1 : Liste
Type Liste
enreg Val : entier
Queue : ^Liste
Fin enreg
2.1.2 Exemple 2 : Arbre
2.1.3 Remarque
Pour traiter des structures récursives on utilise principalement des fonctions récursives
2.2 Exemples d’algorithmes avec les listes
2.2.1 Longueur
Fonction permettant de calculer la longueur (parcours en longueur) d’une liste.
Fonction longueur (val P : ^Liste) : entier
Si P=NULL alors retourner 0
Sinon retourner (1+Longueur(P.^queue))
2.2.2 Somme
Fonction permettant de retourner la somme des valeurs contenues dans la liste. Le principe est le même que pour la fonction Longueur avec : « retourner (P.^val+somme(P.^queue)) ».
2.2.3 Concaténer
Cette fonction permet de concaténer une liste Q à une liste P (on va chercher la fin de P pour y ajouter Q).
Procedure concaténer (ref P, Q : ^Liste)
Si P=NULL alors P :=Q
Sinon concaténer (P^queue, Q)
2.2.4 Fusionner deux liste triées
Fonction fusionner (val : P, Q : ^Liste) : ^Liste
Var temp : ^Liste
Selon que :
Cas P=NULL retourner Q
Cas Q=NULL retourner P
Cas P.^val < Q.^val
Allouer (Temp)
Temp^.val=P^.val
Temp^.queue:=P^.queue
Temp^.queue :=Fusionner(P^.queue, Q)
Retourner Temp
Sinon
… (idem dans l’autre sens)
3 Programmation dynamique
La programmation dynamique est une méthode générale de calcul de plusieurs valeurs dont la plupart dépendent d'autres. Elle est utilisée dans les cas où un algorithme simple naïf serait trop coûteux. Elle consiste à appliquer le principe évident qu'il est inutile de calculer la même chose deux (ou plusieurs) fois. Pour cela, on va stocker les résultats déjà calculés dans un tableau.
3.1 Exemples
3.1.1 Un TRES petit exemple: la suite de Fibonacci
Nous avons vu que la méthode simple récursive n'est pas bonne. Une meilleure méthode consiste à stocker les résultats déjà calculés dans un tableau et ce, jusqu’à la valeur souhaitée :
1 | 1 | 2 | 3 | 5 | … |
3.1.2 Les coefficients binomiaux
Le nombre de façons de choisir m objets parmi n. On connaît tous la formule i :
Une autre méthode consistant à voir si on laisse le premier objet , ou on le prend donne la relation suivante qui pourra être facilement implémentée à l’aide d’un tableau : Bin(n,m)=Bin(n-1,m)+Bin(n-1,m-1) (sauf dans les cas n=m ou n=0).
3.1.3 Le nombre de partitions d'un entier
Supposons que l’on cherche le nombre de façons de diviser n objets identiques en (1 ou) plusieurs parties. Ce calcul peut paraître peu évident car il n’y a pas de récurrence directe. Mais si on ajoute un deuxième paramètre (la taille de la plus grande partie) on trouve une récurrence dont les résultats pourront être stockés :
sauf dans les cas n <= max .
3.1.4 Remarque intermédiaire
Une méthode naïve aurait été de calculer directement la récurrence (peut-être par une fonction récursive) sans utiliser de tableau. Le temps de calcul aurait été déterminé par le nombre de feuilles dans l'arbre de tous les calculs possibles. On peut arriver à des algorithmes qui mettent des siècles à calculer. La programmation dynamique peut réduire la durée de ces calculs à une fraction de seconde.
3.1.5 Un exemple (un peu) moins mathématique faire l'appoint
Je veux calculer le nombre de façons de faire un total de N centimes étant donné le nombre de types de pièces qui existent (n), le nombre que je possède et la valeur en centimes de chaque type (tableaux Nombre et Valeur indicés de 1 à n) .
Calcul de Nombre(Total,i) : le nombre de façons de faire un total de Total centimes en n'utilisant que les pièces des i premiers types :
t:=0; // sera le nombre souhaite
u:=0; // le nombre de pieces de type i utilisees
u:=0; // le nombre de pieces de type i utilisees
repeter
t:=t+Nom(Tot-u*Valeur[i],i-1);
u:=u+1;
jusqu'a u>Nombre[i] ou u*Valeur[i]>Tot
u:=u+1;
jusqu'a u>Nombre[i] ou u*Valeur[i]>Tot
finrepeter;
(sauf les cas i=0 (Nombre(Total,0)=1 ou 0 selon si Total=0)
3.1.6 Un exemple avec temps, probabilité et stratégie: lancer des dés pour finir avec 100 points.
On lance des dés 20 fois. A chaque coup, on gagne le nombre de points sur la face visible du dé. On veut finir avec exactement 100 points. Le calcul consiste à déterminer la probabilité de réussir.
Pour ne pas faciliter le problème, on peut, à chaque coup, choisir de lancer un ou deux dés (de façon à maximiser la probabilité de réussite).
On calcule pour chaque p (nombre de points entre 0 et 100) et chaque c (nombre de coups entre 0 et 20) la probabilité de gagner si on veut encore p points après le c-ème coup, disons P(p,c) (sauf si c=20) :
- Si on lance un dé : probabilité
- Si on lance deux dés: probabilité
- Et on prend le maximum des deux comme valeur de P(p,c).
- Avec correction pour les cas où on essaie de calculer une valeur avec p < 0 !
3.1.7 Le problème du sac à dos discret
Etant donné un sac à dos et n objets de poids et valeur différents, quel est la valeur maximale d'un ensemble d'objets qui ne dépasse pas la capacité (en poids) du sac?
Supposons que l’on considère les objets en ordre et décide, pour chacun, si on le prend ou non. Quand on considère l'objet numéro i, la valeur de ce que l’on pourrai choisir parmi (i+1, n) dépend de la partie non utilisée de la capacité. On calcule donc pour chaque i et chaque capacité (entre 0 et la capacité initiale) une valeur maximale.
3.2 Remarque 1 : Economiser l'espace
Quand la récurrence donne la valeur de la colonne i du tableau comme fonction de la colonne i+1 (ou i-1) on n'est pas obligé de garder tout le tableau. Il suffit de garder deux colonnes à chaque moment (vrai pour les algorithmes de probabilités dans le graphe et le sac-à-dos par exemple)
Si, en outre, chaque élément d'une colonne ne dépend que des éléments de l'autre colonne qui sont en dessus (ou en dessous), il suffit de garder une colonne qui, à chaque moment, peut contenir une partie de l'ancienne colonne et une partie de la nouvelle. (vrai pour le sac-à-dos).
3.3 Remarque 2 : Eviter les calculs inutiles
Il se peut que quelques éléments du tableau ne soient pas utilisés dans le calcul final qui nous intéresse (c'est-à-dire ni directement ni indirectement) mais que la structure du problème soit trop irrégulière pour savoir à l'avance lesquels (par exemple dans le cas de la chaîne de Markov, il est inutile de calculer la probabilité de réussir en 90 transitions à partir de l'état j s'il n'est pas possible d'arriver à cet état en 10 transitions de l'état initial).
Dans ce cas, la programmation dynamique comme décrite fait des calculs inutiles qui n'auraient pas été faits par la méthode récursive citée avant. Mais il est toujours vrai que cette méthode récursive fait BEAUCOUP plus de calculs parce qu'elle fait très souvent le même calcul plusieurs fois.
Il existe une méthode mixte qui ne fait que les calculs utiles et ne les fait qu'une fois: elle consiste à utiliser la structure récursive et un tableau; la première fois qu'un résultat est calculé il est inséré dans le tableau; les fois suivants, cette valeur est récupérée du tableau.
Précédent :Algorithmes de TRI
Suivant : Structures complexes
Article plus récent Article plus ancien
