Conversion de boucles en récursion : explication des modèles et de la récursion de queue

La récursivité et les boucles sont deux outils fondamentaux pour implémenter des tâches répétitives en programmation. Alors que les boucles comme for et while sont intuitives pour la plupart des développeurs, la récursivité offre une approche plus abstraite et flexible de la résolution de problèmes. Cet article explore comment convertir des boucles en fonctions récursives, fournit des modèles généraux et explique le concept et l'optimisation de la récursion de queue.

---

Comprendre la récursivité

Qu’est-ce que la récursivité ?

La récursion est une technique dans laquelle une fonction s'appelle pour résoudre des instances plus petites du même problème. Ce comportement autoréférentiel se poursuit jusqu'à ce qu'une condition de base spécifiée soit remplie.

Par exemple, calculer la factorielle d'un nombre par récursion :

function factorial(n) {
  if (n <= 1) return 1; // Base case
  return n * factorial(n - 1); // Recursive case
}

Dans cet exemple, factorial(n - 1) réduit la taille du problème à chaque appel, se terminant finalement lorsque n vaut 1.

---

Conversion de boucles en récursion

Modèle général pour le remplacement des boucles

Pour convertir des boucles en récursivité, suivez ces étapes :

1. Identifiez l'état de l'itération : déterminez quelles variables changent au cours de chaque itération de boucle (par exemple, des compteurs ou des indices).
2. Définir le cas de base : Spécifiez quand la récursivité doit s'arrêter, analogue à la condition de sortie d'une boucle.
3. Effectuer le travail de l'itération actuelle : Exécuter la logique de l'itération de la boucle actuelle.
4. Appel récursif : progressez vers le cas de base en mettant à jour l'état d'itération.

Modèle

function recursiveFunction(iterationState, dataOrAccumulator) {
  // Base case: Define when recursion stops
  if (baseCondition(iterationState)) {
    return dataOrAccumulator; // Final result
  }

  // Perform the action for the current iteration
  const updatedData = updateAccumulator(dataOrAccumulator, iterationState);

  // Recursive call with updated state
  return recursiveFunction(updateIterationState(iterationState), updatedData);
}

Exemples

Exemple 1 : additionner un tableau

Utiliser une boucle :

function sumArray(arr) {
  let sum = 0;
  for (let i = 0; i < arr.length; i++) {
    sum += arr[i];
  }
  return sum;
}

Utilisation de la récursivité :

function sumArrayRecursive(arr, index = 0) {
  if (index >= arr.length) return 0; // Base case
  return arr[index] + sumArrayRecursive(arr, index + 1); // Recursive case
}

Exemple 2 : compte à rebours

Utiliser une boucle :

function countdown(n) {
  while (n > 0) {
    console.log(n);
    n--;
  }
}

Utilisation de la récursivité :

function countdownRecursive(n) {
  if (n <= 0) return; // Base case
  console.log(n); // Current iteration work
  countdownRecursive(n - 1); // Recursive case
}

---

Comprendre la récursion de la queue

Qu’est-ce que la récursion de queue ?

La récursion de queue est une forme spéciale de récursion où l'appel récursif est la dernière opération de la fonction. Cela signifie qu'aucun calcul supplémentaire n'a lieu après le retour de l'appel récursif.

Exemple de récursion de queue :

function factorialTailRecursive(n, accumulator = 1) {
  if (n <= 1) return accumulator; // Base case
  return factorialTailRecursive(n - 1, accumulator * n); // Tail-recursive call
}

Exemple de récursion sans queue :

function factorial(n) {
  if (n <= 1) return 1; // Base case
  return n * factorial(n - 1); // Recursive case
}

Avantages de la récursion de queue

1. Optimisation de la pile : les fonctions récursives de queue peuvent être optimisées en réutilisant le cadre de pile actuel au lieu d'en créer un nouveau pour chaque appel. Cela réduit l'utilisation de la mémoire et empêche le débordement de pile.
2. Efficacité : la récursion de queue peut égaler les performances des boucles itératives lorsque l'optimisation des appels de queue (TCO) est prise en charge par le moteur JavaScript.

---

Modèle pour la récursion de queue

Pour écrire des fonctions récursives de queue, suivez ce modèle :

1. Mettre l'état d'itération en premier : L'état d'itération (par exemple, compteurs, indices) doit être le premier argument.
2. Utiliser les accumulateurs : utilisez des paramètres supplémentaires pour transporter des résultats intermédiaires.
3. Appel récursif comme dernière opération : assurez-vous que l'appel récursif est la dernière action de la fonction.

Modèle récursif de queue

function recursiveFunction(iterationState, dataOrAccumulator) {
  // Base case: Define when recursion stops
  if (baseCondition(iterationState)) {
    return dataOrAccumulator; // Final result
  }

  // Perform the action for the current iteration
  const updatedData = updateAccumulator(dataOrAccumulator, iterationState);

  // Recursive call with updated state
  return recursiveFunction(updateIterationState(iterationState), updatedData);
}

---

Exemples de récursion de queue

Exemple 1 : Résumation récursive d'un tableau

function sumArray(arr) {
  let sum = 0;
  for (let i = 0; i < arr.length; i++) {
    sum += arr[i];
  }
  return sum;
}

Exemple 2 : Factorielle récursive de queue

function sumArrayRecursive(arr, index = 0) {
  if (index >= arr.length) return 0; // Base case
  return arr[index] + sumArrayRecursive(arr, index + 1); // Recursive case
}

---

Avantages et limites de la récursivité

Avantages

1. Expressivité : la récursivité est plus intuitive pour les problèmes impliquant des structures hiérarchiques ou diviser pour régner, tels que les parcours d'arbres et les recherches de graphiques.
2. Cleaner Code : les solutions récursives peuvent éliminer le code passe-partout, en particulier pour les problèmes complexes.
3. Approche générique : la récursivité peut remplacer les boucles et résoudre des problèmes tels que le retour en arrière, qui sont fastidieux avec les boucles.

Limites

1. Débordement de pile : les fonctions récursives qui ne sont pas récursives ou qui impliquent une récursion profonde peuvent dépasser la limite de la pile d'appels.
2. Performance Overhead : chaque appel récursif s'ajoute à la pile, rendant la récursivité naïve moins efficace que les boucles.
3. Prise en charge limitée du navigateur pour le TCO : tous les moteurs JavaScript ne prennent pas en charge l'optimisation des appels de fin, ce qui limite l'utilisation pratique de la récursivité de fin dans certains environnements.

---

Conclusion

La conversion de boucles en récursivité est une technique puissante qui permet d'obtenir un code plus abstrait et flexible. En comprenant et en appliquant des modèles de récursion, les développeurs peuvent remplacer les constructions itératives par des solutions récursives. L'exploitation de la récursion de queue améliore encore les performances et réduit le risque de débordement de pile, à condition que l'environnement prenne en charge l'optimisation des appels de queue.

La maîtrise de ces concepts ouvre la porte à la résolution d'un plus large éventail de problèmes de manière efficace et élégante.

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!