La Fonction de Récursion en JavaScript

Explication :

• La fonction countDown vérifie si le nombre est inférieur ou égal à 0. Si c’est le cas, elle affiche « Terminé ! » et arrête la fonction.
• Sinon, elle affiche le nombre et appelle countDown avec le nombre diminué de 1.
• La fonction continue à s’appeler jusqu’à ce que le nombre atteigne 0.

Exemple suivant : Calculer la Factorielle

La factorielle d’un nombre est le produit de tous les entiers positifs jusqu’à ce nombre. Par exemple, la factorielle de 4 est 4 × 3 × 2 × 1 = 24.

Explication :

• La fonction factorial vérifie si n est égal à 0. Si oui, elle renvoie 1 (car 0! = 1).
• Sinon, elle renvoie n multiplié par la factorielle de n - 1.
• La fonction s’appelle elle-même avec des valeurs décroissantes jusqu’à atteindre 0.

En mathématiques, la factorielle d’un nombre entier positif

Par exemple, pour calculer la factorielle de 5, notée

5!, vous multipliez tous les entiers de 1 à 5 :

5!=5×4×3×2×1=120

function reverseString(str) {
    if (str === "") { // Cas de base
        return "";
    }
    return reverseString(str.substr(1)) + str.charAt(0); // Cas récursif
}
console.log(reverseString("recursion")); // Affiche "noisrucer"

Calcul du PGCD (Plus Grand Commun Diviseur)

Le plus grand commun diviseur de deux nombres peut être calculé de manière récursive en utilisant l’algorithme d’Euclide.

function gcd(a, b) {
    if (b === 0) { // Cas de base
        return a;
    }
    return gcd(b, a % b); // Cas récursif
}
console.log(gcd(48, 18)); // Affiche 6

Compter les Occurrences d’un Caractère dans une Chaîne

Cette fonction compte combien de fois un caractère donné apparaît dans une chaîne.

function countOccurrences(str, char) {
    if (str.length === 0) { // Cas de base
        return 0;
    }
    let count = (str.charAt(0) === char) ? 1 : 0;
    return count + countOccurrences(str.substr(1), char); // Cas récursif
}
console.log(countOccurrences("recursion", "r")); // Affiche 2

Trouver le Plus Petit Élément d’un Tableau

Voici une fonction récursive pour trouver le plus petit élément d’un tableau.

function findMin(arr, n) {
    if (n === 1) { // Cas de base
        return arr[0];
    }
    return Math.min(arr[n - 1], findMin(arr, n - 1)); // Cas récursif
}

const numbers = [5, 3, 7, 1, 4];
console.log(findMin(numbers, numbers.length)); // Affiche 1

Les grands classiques comme la Tour de Hanoï

Le problème des Tours de Hanoï est un casse-tête mathématique où vous avez trois tiges et un certain nombre de disques de tailles différentes.

Tous les disques commencent sur la première tige, empilés par ordre de taille décroissante. Le but est de déplacer tous les disques vers la troisième tige en respectant les règles suivantes :

1. Vous ne pouvez déplacer qu’un seul disque à la fois.
2. Un disque ne peut être placé que sur un disque plus grand.
3. Vous devez utiliser les trois tiges.

Solution Récursive

La récursion est une méthode idéale pour résoudre ce problème, car chaque mouvement peut être considéré comme un sous-problème plus petit.

Explication de la Fonction hanoi

Voici la fonction en question :

function hanoi(disque, tigeSource, tigeDestination, tigeAuxiliaire) {
  if (disque === 1) {
    // Cas de base
    console.log(`Déplacer le disque 1 de ${tigeSource} à ${tigeDestination}`);
    return;
  }
  // Déplacer disque-1 disques de la tige source à la tige auxiliaire
  hanoi(disque - 1, tigeSource, tigeAuxiliaire, tigeDestination);
  // Déplacer le disque restant vers la tige destination
  console.log(
    `Déplacer le disque ${disque} de ${tigeSource} à ${tigeDestination}`
  );
  // Déplacer les disque-1 disques de la tige auxiliaire à la tige destination
  hanoi(disque - 1, tigeAuxiliaire, tigeDestination, tigeSource);
}
// Exemple avec 3 disques
hanoi(3, 'A', 'C', 'B');

1. Cas de Base : disque === 1

Le cas de base dans la récursion est la condition qui met fin à l’appel récursif. Ici, le cas de base est lorsque disque === 1, c’est-à-dire qu’il ne reste qu’un seul disque à déplacer.

if (disque === 1) {
  console.log(`Déplacer le disque 1 de ${tigeSource} à ${tigeDestination}`);
  return;
}

• Quand cette condition est vraie : La fonction imprime simplement le déplacement du disque 1 de la tige source vers la tige destination.
• Pourquoi c’est important : Cela empêche la récursion de continuer indéfiniment et définit le comportement pour le plus petit sous-problème possible (déplacer un seul disque).

2. Déplacer disque - 1 Disques de la Tige Source à la Tige Auxiliaire

hanoi(disque - 1, tigeSource, tigeAuxiliaire, tigeDestination);

• Que fait cette ligne ? : La fonction appelle hanoi pour déplacer les disque - 1 disques du haut de la tige source vers la tige auxiliaire. La tige destination devient temporairement la tige auxiliaire pour cette opération.
• Pourquoi c’est important ? : Cette étape est cruciale car elle déplace tous les disques sauf le plus grand (le disque actuel) sur la tige auxiliaire, libérant ainsi la tige source pour déplacer le plus grand disque directement vers la tige destination.

3. Déplacer le Disque Actuel de la Tige Source à la Tige Destination

console.log(`Déplacer le disque ${disque} de ${tigeSource} à ${tigeDestination}`);

• Que fait cette ligne ? : Elle imprime l’instruction pour déplacer le disque actuel (le plus grand des disques restants) de la tige source vers la tige destination.
• Pourquoi c’est important ? : Après avoir déplacé les disque - 1 disques plus petits vers la tige auxiliaire, vous pouvez maintenant déplacer le plus grand disque directement vers la tige destination.

4. Déplacer les disque - 1 Disques de la Tige Auxiliaire à la Tige Destination

hanoi(disque - 1, tigeAuxiliaire, tigeDestination, tigeSource);

hanoi(3, "A", "C", "B");

Les fonctions récursives comme celles présentées ici sont non seulement utiles, mais aussi extrêmement puissantes pour résoudre des problèmes qui se prêtent bien à une décomposition en sous-problèmes similaires.

La Tour de Hanoï est un excellent exemple, illustrant comment une solution récursive peut décomposer un problème complexe en étapes simples et répétitives.

Améliore tes compétences dans l’apprentissage de JavaScript pour cela :