Quelle est la méthode d'implémentation de l'algorithme récursif en JavaScript

L'algorithme récursif est une idée d'algorithme courante. Grâce à l'appel de fonctions récursives, les problèmes peuvent être décomposés et résolus. En JavaScript, l'implémentation des fonctions récursives est très simple. Il suffit de faire attention à l'ordre des appels de fonction et aux conditions de sortie.

Ensuite, nous présenterons la méthode d'implémentation de l'algorithme récursif en JavaScript à travers des exemples.

Exemple 1 : Trouvez la valeur du nième terme de la séquence de Fibonacci

La séquence de Fibonacci fait référence à : 0, 1, 1, 2, 3, 5, 8, 13, 21, 34,…, c'est-à-dire le le premier élément est 0, le deuxième élément est 1 et chaque élément suivant est la somme des deux éléments précédents. Ce qui suit utilise un algorithme récursif pour trouver la valeur du nième élément de la séquence de Fibonacci :

function fibonacci(n) {
  if(n <= 1) {
    return n;
  } else {
    return fibonacci(n-1) + fibonacci(n-2);
  }
}

Dans le code ci-dessus, déterminez d'abord si n est 1 ou 0. Si c'est le cas, renvoyez n lui-même comme condition de sortie de la récursion. Si n n'est pas 1 ou 0, décomposez le problème en résolvant la somme des deux premiers éléments et appelez sa propre fonction de manière récursive jusqu'à ce que la condition de sortie soit atteinte.

Exemple 2 : Problème de la Tour de Hanoï

Le problème de la Tour de Hanoï est un problème récursif classique. Le problème est décrit comme suit : Il y a trois piliers, et plusieurs disques de tailles différentes sont placés sur l'un des piliers. Le disque est le plus grand et les autres disques diminuent en séquence. Vous devez maintenant déplacer ces disques vers un autre pilier. Pendant le mouvement, vous devez placer le plus petit disque sur un pilier au-dessus du plus grand disque, et un seul disque peut être déplacé à la fois. Je voudrais demander, lorsque les conditions de déplacement sont remplies, combien de mouvements sont nécessaires pour déplacer tous les disques vers un autre pilier ?

Ce qui suit est l'implémentation de l'algorithme récursif pour le problème de la Tour de Hanoï :

function hannuo(n, A, B, C) {
  if(n === 1) {
    console.log(`将第${n}个圆盘从${A}移动到${C}`);
  } else {
    hannuo(n-1, A, C, B);
    console.log(`将第${n}个圆盘从${A}移动到${C}`);
    hannuo(n-1, B, A, C);
  }
}

Parmi eux, n représente le nombre de disques, A, B et C représentent respectivement trois piliers. La fonction récursive hannuo est. pour déplacer n disques du bas de A. Vers le bas de C, le bas de B doit être utilisé au milieu. Pendant le processus récursif, il est nécessaire de résoudre en continu les sous-problèmes d'échelle réduite jusqu'à ce que la récursion atteigne. le moindre problème : déplacer le premier disque de A vers C. Le résultat final est d'appeler hannuo(n, 'A', 'B', 'C') pour résoudre et afficher les étapes de déplacement.

Les algorithmes récursifs peuvent nous aider à résoudre certains problèmes complexes, mais nous devons également faire attention à éviter une récursivité infinie, nous devons donc être prudents lors de l'écriture de code.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!