Recursion suite: Algorithme d'Euclide et Tours de Hanoi

Algorithme d'Euclide:

L'algorithme d' Euclide permet de déterminer le pgcd de la manière suivante:
- pgcd(a, a) = a,
- pgcd(a, b) = pgcd(a − b, b) si a > b ou pgcd(a, b − a) si a

Programmez l'algorithme d'Euclide de façon récursive.
Nota bene une autre méthode pour calculer l'algorithme d'Euclide est l'opérateur modulo "%"
pgcd (a,b) = b si a%b == 0 , ou sinon (a%b) % b ;

function pgcd(a,b){
 return  a>b && pgcd(a-b, b)|| a<b && pgcd(a,b-a) || a===b && a ; 
}
//Et avec l'opérateur modulo :
function pgcd(a,b){      
   return  a>b && a%b>0 && pgcd(b,a%b) || (b>a)&& pgcd(b,a) || a%b===0 && b ;
}
pgcd(2736,486144);//30

Ici on utilise volontairement les expressions javascripts pour raccourcir l'écriture, ce qui n'est pas forcément toujours à conseiller. Pour les matheux, un problème plus complexe est de calculer les coefficients de Bezout, Ces coefficients sont très utiles dans le cryptage des données.

Tours de Hanoi :

Voici (enfin) l'incontournable problème qui illustre la récursivité, ce problème a été inventé au début du siècle par un mathématicien français afin d'illustrer la résolution d'un problème par récursivité.
Attention, essayez de comprendre ce problème et sa solution... c'est un problème fondamental, il vous permettra de comprendre les autres solutions par récurrence même si vous avez étudié la récurrence dans vos études !
Dans un temple bouddhiste, à Hanoi 3 mâts sont disposés en ligne l'un à côté de l'autre. Sur le mât de gauche sont empilés des disques d'or très lourds, percés au centre, de diamètre variable, et ordonnés du plus grand au plus petit.
Un moine est chargé de transférer ces disques sur le troisième piquet à droite, avec cependant un impératif: il ne doit jamais déposer un disque d'un diamètre supérieur aux disques précédents sur un mât donné.
La légende dit que la fin du monde surviendra lorsque le moine aura terminé son travail...
Pouvez vous programmer un mode d'emploi pour aider notre moine dans sa tache interminable ? Il faut écrire un programme qui donne
hanoi( ndisques, "gauche", "droite", "milieu")
qui permet à notre moine de savoir de transférer ndisques de gauche à droite, en s'aidant du mât du milieu .

Réponse:
Le principe de récurrence dit que si vous pouvez le faire pour 1 élément et si vous savez passer de l'élément n à n-1 alors vous savez résoudre le problème ! ....
Ainsi on suppose que vous savez passer une colonne de n-1 disques de gauche au milieu ou à droite.. comment passer une colonne de n disques de gauche à droite :
passer une colonne entière de n-1 disques de gauche au milieu, // vous prétendez que vous savez le faire
passer le disque large de la base de gauche à droite // vous savez le faire pour de bon !
puis repasser la colonne de n-1 disques du milieu à gauche... // vous prétendez savoir le faire

var r=[];  // le résultat sera dans un tableau .
function hanoi (n,g,d,m){
    if(n==0) return r ;
    hanoi(n-1, g,m,d);
    r.push( "Faire passer le disque de " + g  + " à   " + d );
    hanoi(n-1,m,d,g) ;
 }
hanoi(10,'Gauche', 'Droite', 'Milieu') ;
r ;

Le programme des tours de Hanoi, n'est pas un simple jeu ni un puzzle, c'est l'illustration même de la récursivité. Votre travail ici est de passer de n disques à n-1 disques , d'une part et d'autre part de savoir quand cela doit s'arrêter, ici lorsqu'il n'y a plus de disque à déplacer. C'est tout .
Prenez donc le temps de comprendre ce programme il vous permettra de comprendre la magie de la récursion. C'est particulièrement utiles dans les programmes du type anagrammes ou comptage des parties d'un ensemble.