La récursivité est sans doute l'un des concepts que la plupart des gens ont le plus de mal à comprendre, je vais donc commencer par vous fournir une définition toute simple de ce qu'est une fonction ou une routine récursive.
Une fonction est dite «récursive» quand elle est en mesure de s'appeler elle-même.
Hé bien, cela n'a pas l'air si compliqué à comprendre, et pourtant…
La grosse difficulté du concept ne vient pas de sa compréhention (finalement assez facile), mais bien de son application…
Pour comprendre correctement la récursivité, il s'agit non pas de comprendre comment l'utiliser, mais bien pourquoi l'utiliser.
Le principal problème que l'on rencontre lorsque l'on essaie d'expliquer la récursivité est qu'il n'y a pas, à proprement parler, d'exemples qui puissent montrer simplement comment l'utiliser, que de nombreux exemples pourraient parfaitement être résolus, bien souvent de manière plus rapide, plus simple et plus efficace, par la simple utilisation d'itération telles que les boucles pour ou boucles tant que.
De cette manière, on peut très bien envisager d'utiliser la récursivité pour déterminer la puissance N d'une valeur, ou la factorielle (valeur de la multiplication de chacun des nombres qui précèdent le nombre visé) d'un nombre, mais il apparaît très clairement que la simple création d'une boucle de type "pour" ou de type "tant que" serait au minimum tout aussi facile à mettre en oeuvre…
Par contre, il devient presque inimaginable d'envisager la création de certains algorithmes sans faire appel à la récursivité dans certaines conditions, telles que l'utilisation d'arbres, la mise au point d'une "tour d'Annoï".
Le pire dans l'histoire, c'est qu'il est très difficile d'échaper en permanence à la récursivité…
Bien sûr, vous pourriez tout à fait ignorer le concept, et d'ailleurs prétendre que vous n'en avez pas besoin, mais vous passeriez alors à côté d'un potentiel énorme vous permettant de générer le «Saint Graal» du programmeur: l'intelligence artificielle, même si celle-ci devait n'être qu'excessivement basique.
Le principal problème, quand on décide d'utiliser la récursivité, c'est que, comme pour les boucles de types "Tant Que" ou de type "Jusque", si l'on n'y prend pas garde, il est très facile de créer une fonction dont on ne sortira jamais…
S'il est généralement embêtant de rentrer dans une boucle dont on ne sort pas (car cela provoque la nécessité de tuer violemment l'application en cours), il faut savoir que le fonctionnement même de l'appel de fonctions est en mesure de provoquer des désagréments encore bien plus importants…
En effet, lorsque l'on appelle une fonction, les valeurs actuelles des différentes variables sont mises dans une pile (appelée «stack») de manière à pouvoir être récupérées une fois que la fonction a été achevée, et permettre ainsi de continuer où on en était resté avant l'appel de la fonction.
Cela signifie que, chaque fois que la fonction s'appellera elle-même, elle mettra une certaine quantité d'informations dans la pile, pour pouvoir les récupérer par la suite.
Pour notre plus grand malheur, la pile (stack) n'est pas infinie, et, si l'on place trop d'informations dedans, on finit par obtenir l'erreur honnie entre toutes: le fameux «Stack Overflow», ou dépassement de pile, source de bien des malheurs pour ceux qui y sont confrontés.
Le seul moyen de s'assurer qu'on sortira effectivement de la récursivité à un moment ou un autre, c'est de tester ce que l'on appelle le «cas de base» ou, si vous préférez, le cas qui provoquera forcément le renvoi d'une valeur, ou à défaut, qui ne provoquera pas ne nouvel appel récursif.
Cependant, même avec l'utilisation du cas de base, s'il y a définitivement trop d'appels récursif avant d'arriver au cas de base, ou que l'on place définitivement trop de valeurs dans la pile (fixme: est-ce seulement les valeurs de pointeurs d'instructions et de registre, ou est-ce les valeurs de toutes les variables?), le risque reste présent d'arriver à un dépassement de pile
De manière à bien vous faire comprendre ce qu'est la récursivité, je me propose de vous présenter pour commencer deux types de calculs pour lesquels elle n'est pas indispensable.
Le premier calcul est celui de la factorielle d'un nombre.
La factorielle d'un nombre est la multiplication de tous les nombres non nuls qui précèdent ce nombre, le nombre étant inclus.
Par exemple, la factorielle de 5 (notée habituellement 5!) est 1*2*3*4*5=120.
Bien sûr, il est tout à fait possible, et presque plus facile, d'utiliser une simple itération (une boucle pour ou une boucle tant que) pour effectuer un tel calcul, comme le présente le nassichneiderman ci-dessous
Et, d'une certaine manière, essayer d'utiliser la récursivité pour un tel usage, revient à se taper avec un marteau sur la tête, sans compter que, du point de vue des pures performances, l'appel à de nombreuses fonctions (même si c'est tout le temps la même qui est appelée) sera catastrophique…
Un exemple tout aussi peu utile de récursivité serait de vouloir calculer la valeur de X à la puissance N (d'obtenir la valeur de XN)
Elever un nombre à une puissance donnée revient à le multiliper par lui-même un nombre de fois correspondant à cette puissance
Par exemple, si l'on souhaite élever le nombre 3 à la puissance 4 (calculer 34), on fera tout simplement (1*)3*3*3*3=81.
Vous remarquerez d'ailleurs que j'ai fait exprès de mettre un multiplicateur supplémentaire (qui ne change rien à la valeur) de 1* entre parenthèse…
C'est uniquement pour vous rappeler que, quel que soit le nombre, X0 donne …1.
Pour l'élévation d'un nombre à une puissance donnée, on pourrait très facilement se contenter d'un algorithme tout simple d'itération dans le genre de
Tout en émettant exactement les mêmes critiques par rapport à l'idée de créer cette fonction de manière récursive que pour la factorielle.
On pourrait d'ailleurs encore trouver bien d'autres exemples pour lesquels il serait possible de créer une fonction récursive, mais pour lesquels la récursivité ne se justifie pas autrement que par la beauté du travail intellectuel qu'elle peut représenter…
Par contre, ces deux exemples vont, je l'espère, vous permettre de comprendre exactement ce que représentent la récursivité et les termes «chercher le cas de base»…
En effet, calculer la factorielle d'un nombre (en utilisant la notation scientifique habituelle, on écrit N!) ne revient ni plus ni moins à multiplier la factorielle de N-1 par ce nombre (N!=(N-1)!*N)
En d'autres termes, si on cherche 5!, et qu'on connait déjà 4!, on peut se contenter de faire 4!*5…
Or 4! n'est rien d'autre que 3!*4, et 3! n'est rien d'autre que 2!*3, 2! n'est rien d'autre que 1!*2 et 1! vaut… 1
Pour ceux qui ne seraient pas familiarisés avec la notation scientifique, la factorielle de 5 n'est autre que la factorielle de 4 multiplliée par 5, la factorielle de 4 n'est autre que la factorielle de 3 multipliée par 4, celle de 3 n'est autre que la factorielle de 2 multipliée par 3 et la factorielle de 2 n'est autre que la factorielle de 1 multipliée par 1… Mais comme il n'y a pas de nombre entier non nul en dessous de 1, la factorielle de 1 est 1 (pfiou)
De la même manière, s'il s'agit de calculer Xn , cela revient à calculer Xn-1*X…
Calculer 54 revient à calculer 53*5, mais calculer 53 reveint à calculer 52*5, calculer 52 revient à calculer 51*5 et calculer 51 reveint à calculer 50*5… Or 50 vaut 1 (comme n'importe quel nombre élevé à la puissance 0).
«Rechercher le cas de base», pour ces deux exemples, n'est rien d'autre que le fait que rechercher le test qui permet de renvoyer une valeur qui permet, non seulement de ne pas modifier un résultat donné, mais aussi de calculer les valeurs suivantes…
Toute personne qui a réussi ses études primaires sait que le fait de multiplier un nombre par 1 ne change pas ce nombre…
Comme les deux exemples que je vous présente ne sont jamais que des multiplications, et qu'il est possible d'en arriver à un moment donné à multiplier par 1, le cas de base est tout trouvé pour chacun des exemple…
Voici les nassichneiderman du calcul des factorielles et des puissance transformés en fonctions récursives:
On effectue d'abord un test pour savoir s'il faut arreter ou non d'effectuer les appels récursif.
Si Nombre n'est pas égal à 1 (pour la factorielle) ou que Exposant n'est pas égal à 0 (pour la puissance), c'est donc qu'il y a lieu d'effectuer au minimum un appel récursif suplémentaire (à vrai dire, il aurait presque été intéressant de faire la vérification sur plus petit ou égal, pour éviter les erreurs dues à des gens demandant la factorielle de -5).
Cest test nous envoient, s'il donnent une réponse "vraie", directement vers ce fameux cas de base…
La valeur de travail effectue alors la multiplication du nombre par le résultat de l'appel récursif, et renvoie la valeur à la fonction appelante.
Mais… A voir vos têtes, je ne serais pas surpris que la plupart d'entre vous soient relativement sceptiques quant au raisonnement suivi, et décident d'agir comme Saint Thomas en ne croyant que ce qu'ils voient…
Voici donc la preuve que ces algorithmes fonctionnent…
Le meilleur moyen de s'assurer qu'un alogrithme fonctionne, est d'essayer de le suivre en fournissant une valeur choisie au hazard, tout en veillant quand même, dans la mesure du possible à ne pas devoir le parcourir de *trop nombreuses fois*.
Pour l'exemple, je vais m'en tenir au calcul de la factorielle de 5… mais rien n'interdit à quiconque d'essayer avec une factorielle plus importante…
Nous arrivons donc dans la fonction avec Nombre vallant 5…
Comme je l'ai indiqué, nous ferions un calcul du genre de 1*2*3*4*5=120, où, la multiplication étant du genre de 5*4*3*2*1=… toujours 120.
Le test vérifie si Nombre vaut 1… Ben non, on vient de dire qu'il vaut 5…
On passe donc du coté "N" du test, et là, on dit d'appeler la fonction avec une valeur de (Nombre-1) soit, 4…
On revérifie (avec Nombre valant 4) si Nombre vaut 0… Ben non, toujours pas…
On passe donc de nouveau du coté "N" du test, et, comme c'est bizard, on doit retourner dans la fonction avec une valeur de (Nombre-1) 3.
Au troisième passage, Nombre ne vaut toujours pas 1, donc on retourne du coté "N" du test, et on appelle la fonction avec une valeur de 2 (Nombre, valant 3, -1)…
Pas de bol, Nombre ne vaut toujours pas 1… on passe encore une fois du coté "N" du test, et on appelle encore une fois la fonction en lui passant la valeur 1 (ben oui, Nombre vaut 2, et on passe Nombre-1… jusqu'à preuve du contraire, 2-1=1).
Cette fois-ci, Nombre vaut bien 1… la fonction renvoie donc la valeur 1…
Cette valeur 1 est renvoyée à la fonction qui avait appelé (donc à l'appel de la fonction pour lequel la valeur était deux).
La valeur de nombre (2 pour ce point-ci) est mutlipliée par la valeur renvoyée par la fonction (1).
Le résultat (2*1) est renvoyée à la fonction appelante (celle où Nombre vallait 3)
Nombre (de valeur 3) est multiplié par le résultat renvoyé par la fonction qu'on vient de quitter (qui, rappelons le, renvoyait 2*1=2)
Nombre vaut donc maintenant 3*(2*1)=6 et il est renvoyé à la fonction appelante, qui n'est autre que factorielle avec une valeur pour nombre de 4…
La valeur de Nombre (4) est multipliée avec le résultat renvoyé par la fonction qu'on vient de quitter (pour rappel: 1*2*3=6).
Nombre vaut donc 4*6=24
Cette nouvelle valeur de Nombre (24) est renvoyée à la fonction appelante, à savoir factorielle, ayant comme argument Nombre=5…
La valeur (5) de Nombre est multipliée par 24 (qui n'est autre que le résultat renvoyé par la fonction factorielle(4), et qui est en fait 1*2*3*4)
Nombre vaut donc à ce moment précis 24*5=120 et est renvoyé à la fonction appelante (on va dire à notre application)
Quand on sort de ces appels récursifs, et en considérant avoir donné un valeur pour Nombre égal à 5, nous obtenons bel et bien le résutat attendu, à savoir 120…
Imaginons que nous voulions effectuer le calcul "extrèmement compliqué" de 23…
Tout le monde devrait être capable de le faire, si pas mentalement, en tout cas par écrit, parce que ce n'est rien d'autre que le calcul de 2*2*2…
Voyons voir si l'algorithme que j'ai mis au point fonctionne sur ce calcul, ceux qui ne seraient pas convaincus pouvant le tester en élevant n'importe quel nombre à n'importe quelle puissance, et, au besoin, en vérifiant à l'aide d'une caculatrice.
L'application appelle donc la fonction "puissance(2,3)", vu qu'elle passe le nombre en premier paramètre, et la puissance en second.
Comme Exposant (qui vaut 3) n'est pas égal à 0, on passe du coté "N" du test
On doit donc appeler Puissance() en fournissant Nombre (qui ne change pas) et Exposant-1 (Exposant vallant 3, on passera donc 2)
Nombre (2) et Exposant(3)sont utilisés dans la formule pour l'appel à la fonction qui prend la forme finale de Puissance(2,2)…
Comme Exposant (qui vaut maintenant 2) n'est toujours pas égal à 0, on passe de nouveau du côté "N" du test
Encore une fois, on appelle la fonction Puissance, en lui donnant les valeurs de 2 pour Nombre et de 1 (2-1) pour Exposant…
Comme Exposant (qui vaut maintenant 1) n'est toujours pas égal à 0, on passe une fois de plus dans la partie "N" du test
On appelle (ici, je le sais, mais ce sera en réalité déterminé plus tard) une dernière fois la fonction Puissance, en passant cette fois-ci les valeurs 2 pour Nombre (ça, ça n'a jamais changé) et 0 (car, pour ceux qui l'ignoreraient, 1-1=0) pour Exposant…
Cette fois-ci, Exposant vaut 0… on passe donc du coté "O" du test…
Du côté "O" du test, on lui dit de renvoyer 1, ben, c'est donc ce que fait la fonction…
Elle renvoie 1 à la fonction qui l'a appelée (autrement dit à Puissance(2,1))
Puissance(2,1) multiplie Nombre (qui vaut 2) par le résultat renvoyé par la fonction qu'elle a appelée (autrement dit: 1) Elle place le résultat de cette multiplication dans une variable nommée Total, et renvoie Total (qui vaut 2*1) à la fonction qui l'a appelée (autrement dit à la fonction Puissance(2,2))
Puissance(2,2) récupère la main et effectue alors le calcul de Total=la_valeur_renvoyée_par_Puissance(2,1) *Nombre
Comme la_valeur_renvoyée_par_Puissance(2,1) vaut 2 et que Nombre vaut 2, Total prend fatalement la valeur de 2*2=4…
Et Total est renvoyé à la fonction qui a appelé Puissance(2,2), c'est à dire à Puissance(2,3) qui récupère la main et effectue le calcul suivant: Total=la_valeur_renvoyée_par_Puissance(2,2)*Nombre.
Comme la_valeur_renvoyée_par_puissance(2,2) est 4 (en fait 2*(2*(1)))), et que Nombre vaut 2, cela revient à faire le calcul Total=2*4 donc, Total vaut 8, valeur renvoyée à la toute premiere routine qui a provoqué l'appel récursif (autrement dit, à l'application), qui n'a plus qu'à l'utiliser.
Pour ceux qui n'auraient pas tout suivi, l'une des seules choses qu'il me reste à faire, c'est présenter un schéma de la manière dont ces deux exemples fonctionnent (on commence par descendre en suivant les doubles flêches, puis on remonte en suivant les flêches simples)
Comme je l'indiquais plus haut, la mise au point d'un simple algorithme d'itération est sans doute bien préférable à la mise au point d'un algorithme récursif pour de telles fonctions… Qu'il vous suffise de constater qu'on travaille énormément avec la pile (stack) pour vous en convaincre, sans compter que le code d'itération n'est finalement pas plus compliqué que celui avec récursivité.
Par contre, il existe des cas pour lesquels les algorithmes récursifs, bien qu'un peu plus lents que les itérations, présenteront un avantage certain du point de vue de la programmation.
Le jeux des Tours d'Hannoï en est un exemple.
Le jeu des tours de Hannoï a été créé il y a une bonne centaine d'années par un mathématicien du nom de Edouard Lucas.
Dans ce jeu, il y a trois "pilliers", et un certain nombre de disques de différents diamètres sont placés sur le pilier de gauche.
La figure ci-dessous présente le jeu, avec trois disques, lors du début de la partie.
Le but de ce jeu est relativement simple: il s'agit "simplement" de faire passer les trois disques du pillier 1 vers le pillier 3 de manière à ce qu'ils se trouvent dans le même ordre (donc, selon les couleurs de mon dessin, le rouge en dessous, le jaune au milieu et le gris en haut).
Pour ce faire, il n'y a que deux règles qui doivent impérativement être respectées:
Résoudre ce problème, du moins tant qu'il s'agit de ne le faire qu'avec trois disques, ne pose à priori pas énormément de problèmes:
Il faut donc 7 déplacements pour résoudre notre tour de Hannoï avec 3 disques…
L'astuce est que, si l'on souhaite la résoudre avec 4 disques, il nous faudra 15 déplacements… et, de manière générale, on peut considérer qu'en demandant de la résoudre avec N disques, il faudra 2N-1 déplacements…
Maintenant que les tours de Hannoï n'ont plus de secrets pour vous, il ne reste plus qu'à créer un algorithme qui permette de les faire résoudre par quelque chose d'aussi bête qu'un ordinateur, et, de préférence, quel que soit le nombre de disques envisagé.
Si vous y tenez réellement, vous pouvez toujours essayer de mettre un algorithme utilisant les itérations au point, mais vous risquez d'y passer beaucoup de temps, et vous garderez la loi de Murphy (plus communément connue sous le nom de «Loi de la Vexation Universelle»), dont l'une des applications en informatique est que «Si vous disposez d'un algorithme capable de gérer N éléments, vous trouverez toujours un imbécile pour demander d'en gérer N+1», pendue comme le glaive de la Justice au dessus de votre tête.
La meilleure solution pour arriver à résoudre ce problème passe par l'utilisation de fonctions récursives…
Si je présente les déplacement ainsi, ce n'est pas uniquement pour épargner votre bande passante, ni pour éviter d'avoir une page trop longue…
C'est surtout parce que cette manière de présenter les déplacement vous permet de vous rendre compte qu'il devrait y avoir moyen de présenter les choses avec trois instructions au lieu de 7 (une par déplacement)
Le fait même de parler de pillier 1, de pillier 2 et de pillier 3 nous empêche de voir la pleine étendue des possiblités…
Enfin, il faut non seulement trouver le moyen de le faire fonctionner avec trois disques, mais avec un nombre inconnu de disques.
Nous allons donc considérer de travailler avec N disques, en sachant qu'il faut les faire passer du pillier de départ, au pillier d'arrivée, et que la seule chose dont on dispose sera un pillier "de travail".
Nous allons donc, logiquement, nommer les pilliers resectivement Depart, Arrivee, et Travail.
Nous pouvons donc synthétiser nos mouvement de la sorte:
Malheureusement, les règles de la tour de Hannoï nous interdisent de déplacer plus d'un disque à la fois…
Il s'agit donc de rentrer de plein pied dans la récursivité.
En effet, si N-1 disques représentent plus d'un disques à mettre sur le pillier de travail, il s'agira en fait d'en mettre N-2 sur le pillier d'arrivée (de manière à pouvoir mettre le N-1 sur le pillier de travail, et, par la suite)
Il s'agira de remonter comme cela, en alternant le pillier de travail juqu'à ce qu'il n'y ait qu'un seul disque à déplacer vers le pillier "Travail" correspondant.
Une fois ce premier disque déplacé, nous pourrons déplacer celui qui se trouvait en dessous du premier (le deuxieme, en somme) sur le seul pillier (à part son point de départ) qui soit accessible (du fait qu'un pillier prend contient de toutes facons le disque le plus petit).
Comme il faut pouvoir bouger le troisième disque, mais que les deux pilliers contiennent des disques plus petits que lui, il s'agit de mettre le plus petit des deux sur le plus gros.
Nous pouvons alors mettre le troisème en place, avant de recommencer un tour pour avoir acces au deuxième, et, de proche en proche, en arriver à avoir N-1 disque sur le pillier de travail, pour mettre le disque N sur son pilliler définitif.
Comme le but de la routine que je vous présente est simplement de résoudre cette tour de Hannoï et que j'ai déjà exprimé en long, en large et en travèrs ce que cela représente, je vais exceptionnellement faire l'impasse sur la première partie du travail qui consiste à exprimer clairement le but de l'application.
Je ferai également l'impasse sur le nassichneiderman de la routine principale qui n'a pour seul but que de demander le nombre de disques en jeu, et d'appeler notre routine récursive (nommée, pour l'occasion Hannoi, qui l'eut cru).
| Nom | Type | Description |
|---|---|---|
| Nombre | Entier | Nombre de disques à bouger |
| Depart | Entier | numéro du pillier sur lequel se trouvent les disques au départ |
| Arrivee | Entier | Numéro du pillier sur lequel on souhaite voir arriver les disque |
| Travail | Entier | Numéro du pillier laissé libre pour le travail |
Donner des explications sur le fonctionnement d'une routine récursive est souvent des plus malaisés, surout quand il s'agit d'expliquer justement l'appel récursif…
Comme je l'indiquais dans l'introduction, la question de savoir "comment fonctionne la récursivité" est souvent facultative pour la compréhension par rapport à celle de savoir "pourquoi utiliser" la récursivité.
En effet, au moment de l'appel, non seulement, on modifie une valeur en vue de tendre vers le cas de base, mais, si plusieurs paramètres sont envoyés, il n'est pas rare que leur ordre soit modifié, de manière à ce que la valeur d'un paramètre serve pour un autre paramètre dans la fonction appelée, comme c'est le cas sur ce nassicheiderman.
Vous aurez sans doute remarqué que, dés que je parle de récursivité, je commence par un test qui, bien souvent effectue bien plus d'actions dans sa partie "Non" que dans sa partie "Oui", et ce, en contradiction avec le conseil que je vous donne sur la page ayant trait au nassichneiderman d'essayer, dans la mesure du possible, de tourner les tests de manière à ce que la plupart des actions à effectuer se trouvent du côté où le test est vérifié.
Il n'est nullement question de se contredire, mais, malheureusement, le concept même du cas de base veut que, théoriquement ce sera le cas où il y aura le moins d'instructions à faire, vu que le but des fonctions récursives est, justement, de tendre vers ce cas de base.
L'astuce, mais c'est une optique que je ne veux imposer à personne, c'est que j'aime avoir la gestion du cas de base en priorité, ce qui m'assure au moins déjà, sous réserve que le reste du code tende effectivement vers ce cas de base, que tôt ou tard la routine arrivera à son terme.
Il est, à mon sens du moins, beaucoup plus embêtant d'oublier de gérer le cas de base que d'avoir un code dont la grosse majorité se trouve dans la partie d'un test où la condition s'est avérée fausse.
En effet, si, pour une raison ou une autre, on ne force pas à sortir de la routine récursive quand le cas de base est atteint, on court purement et simplement à la catastrophe, avec le fameux et honni «stack overflow» qui arrivera toujours trop tôt à notre gout.
Ceci dit, rien ne vous oblige ici à suivre mon exemple, et, si vous préférez effectivement veiller à ce que la grosse majorité du code se fasse du côté "vrai" du test, rien ne vous interdit de simplement l'inverser… Il faudra cependant éventuellement veiller à ce que ce soit correctement l'inverse, selon la présence ou non d'un signe représentant le "ou égal"…
L'explication la plus simple à fournir sur ce nassichneiderman est le test en tout début d'algorithme…
Ce test a simplement pour but de vérifier si on a atteint le cas de base ou non (comme expliqué plus haut, j'aime à savoir que la vérification est faite, et tant pis si je me trouve avec un code dans lequel la grosse partie du travail est effectuée dans la partie "faux" du test).
Le premier appel récursif à la routine a pour but de libérer le disque géré par la routine qui a la main
L'instruction d'affichage correspond en fait à toute la gestion de déplacement du disque que l'on vient de libérer.
S'il y avait, par exemple, un tableau de disques déclaré (c'est presque obligatoire) comme variable globale, et qu'il faille remettre à jour le pillier sur lequel se trouve le disque, cela se ferait ici.
Le deuxieme appel récursif de la routine a pour but de regrouper les disques les plus petits, dans l'ordre, au dessus du disque qu'on vient de libérer et de déplacer.
Comme ce n'est pas forcément très clair, je vous propose de vous présenter "en pas à pas" les actions entreprises par les différents appels de la routine.
Nous avons donc 4 variables, correspondant dans l'ordre au nombre de disques à déplacer (donnons lui la valeur "3", pour la facilité), au pillier de départ (donnons lui logiquement la valeur "1"), au pillier d'arrivee (c'est le pilliler 3, donc on lui donne la valeur "3") et au pillier de travail (c'est le pillier central, donnons lui donc la valeur "2")
(1) Au premier appel, nous avons donc les valeurs suivante:
(2) Une fois le test sur le cas de base effectué (je ne reviendrai plus dessus, vous saurez déterminer quand nombre vaudra zero), on appelle la routine en donnant les valeurs suivantes:
(3)On effectue le test, et on appelle la routine, cette fois ci avec les valeurs
(4)On effectue le test, et on appelle la routine avec les valeurs
Cette routine ne fait rien, du fait qu'on est arrivé au cas de base…
C'est donc (3) qui reprend la main.
(3) déplace son disque (le Numéro 1) de son point de départ (1) vers son point d'arrivée calculé (3)
(3) appelle alors la routine (4') avec les valeurs
(4') ne fait rien, car on est au cas de base.
Comme (3) est terminé apres cet appel, on remonte à (2)
(2) déplace le disque numero 2 de son point de départ (1) vers son point d'arrivee (2), puis appelle (3') en lui passant les valeurs
(3') Appelle donc une routine (qui ne fera rien car en cas de base), puis déplacera le disque 1 de 3 (c'est effectivement bien là qu'il est) vers 2, et rappellera une routine qui sera sans effet car, à nouveau en cas de base.
Il rendra alors la main à (2).
Arrivé à ce stade, (2) est fini, et on en est à la situation suivante:
Disque 3 (le plus gros) sur le pillier 1 (le pillier de départ général)
Disque 2 en dessous de disque 1 (ce qui est autorisé, disque 2 étant plus gros que disque 1) sur le deuxième pillier,
Acun disque sur le pillier 3 (qui est le pillier de destination finale)
(1) reprend la main et, justement, déplace le disque 3 (valeur de Nombre) du pillier 1 (valeur de Depart) sur le pillier 3 (valeur de Arrivee).
(1) appelle ensuite (2') en lui donnant les valeurs
Comme ce n'est pas le cas de base, (2') fait un nouvel appel à (3''), avec les valeurs
(3'') fait un appel ( avec le cas de base), récupère donc la main tout de suite, déplace le disque 1 du pillier 2 (valeur de "Depart" pour cet appel de la routine, mais valeur de "Travail" général) ver le pillier 1 (valeur de "Arrivee"pour cet appel de la routine, mais valeur de "Depart général), et refais un appel avec le cas de base. (3'') s'arrete donc ici, et (2') reprend la main
Il déplace donc le disque 2 du pillier 2 (pillier de départ pour cet appel, mais pillier "de Travail" général) vers le pillier 3 (pillier d'arrivée pour cet appel ET pillier d'arrivée général)
Alors que (2') a encore un apple à effectuer (vers 3'''), nous avons donc, si nous regardons du point de vue général, le disque 1 (le plus petit) sur le pillier 1 (pillier de départ génral) et les disques 2 et 3, dans le bon ordre, sur le pillier 3…
L'apple de (2') effectué à (3''') lui passe les valeurs
(3''') appele la fonction en cas de base, ce qui fait qu'il récupère tout de suite la main et déplace le disque 1 du pillier 1 vers le pillier 3
Il rappelle une derniere fois la fonction en cas de base, puis, 3''' est quitté
2' récupère la main, mais n'a plus rien à faire et est donc quitté
1 récupère la main, mais n'a plus rien non plus à faire et est donc quitté
L'application reprend la main après avoir effectué la routine de manière récursive.
Pfiuuu… Voilà, nous sommes arrivés au bout…
Comme vous pouvez le constater, toute la beauté du geste dans une routine récursive réside dans le nombre pour ainsi dire infini d'actions qui peuvent être entreprises sur base de seulement quelque lignes de code.
Outre, évidemment, la beauté du raisonnement, il faut cependant bien se rendre compte que l'utilisation de la récursivité risque d'occasionner quelques soucis, de risque de dépassement de pile, entre autre, et de demander bien plus de temps que la simple utilisation de boucles d'itérations du fait, justement, de la mise en pile et de la récupération des valeurs dans la pile.
D'un autre côté, la récursivité permet très clairement dans certains cas, du moins, de créer des algorithmes beaucoup plus simples, mais nécessitant plus de réflexion, que ne pourraient l'être des algorithmes ne l'utilisant pas (si quelqu'un arrive à créer un algorithme pour les tours de Hannoï sans utiliser la récursivité, il peut sans problème me le transmettre, je l'étudierai avec plaisir), et peut même parfois représenter le seul moyen d'arriver à un résultat correct.
L'idéal, quand on décide de se tourner vers la récursivité pour résoudre un problème donné, serait, bien que ce ne soit pas *forcement* le cas dans les différents exemples que je vous ai cités sur cette page, d'essayer d'utiliser un minimum de variables et d'effectuer un maximum de traitements, si possible autres que, justement, l'appel à la récursivité.
De cette manière, vous arriverez à rentabiliser au mieux le temps nécessaire à la mise en pile et à la récupération des informations, temps qui reste stationnaire, en fonction du nombre de donneées à placer et/ou récupérer…
Comme tout ce que j'ai pu écrire dans ce tutorial, la récursivité n'a pas pour ambition de se présenter comme la «solution ultime» à tous vos problèmes, ni même comme la «meilleure solution», et encore moins comme «la solution tellement tordue qu'il vaut mieux l'oublier».
Comme tout ce que j'ai écrit dans ce tutorial, la récursivité est simplement «une solution qui peut être très adaptée à une situation donnée, et tout à fait inadaptée dans une autre situation», autrement dit «une solution parmi d'autres» qui *peut valoir la peine* de s'y attarder.
Copyright (©) 2005 (Philippe Dunski)
Ce cours est libre, vous pouvez le redistribuer et/ou le modifier selon les termes de la Licence Publique Générale GNU publiée par la Free Software Foundation (version 2 ou bien toute autre version ultérieure choisie par vous).
Ce cours est distribué car potentiellement utile, mais SANS AUCUNE GARANTIE, ni explicite ni implicite, y compris les garanties de commercialisation ou d'adaptation dans un but spécifique. Reportez-vous à la Licence Publique Générale GNU pour plus de détails.
Cependant, l'auteur apprécierait grandement que vous lui fassiez part de toute modification apportée à son contnu
Vous pouvez le contacter par mail à l'adresse koala01@free.fr
Vous pouvez trouver une adaptation française de la licence GNU/GPL à l'URL http://www.linux-france.org/article/these/gpl.html
