Implémentation récursive des fonctions C++ : existe-t-il une limite à la profondeur de récursion ?

La profondeur de récursion des fonctions C++ est limitée, le dépassement de cette limite entraînera une erreur de débordement de pile. La valeur limite varie selon les systèmes et les compilateurs, mais se situe généralement entre 1 000 et 10 000. Les solutions incluent : 1. Optimisation de la récursion de queue ; 2. Appel de queue ; 3. Implémentation itérative ;

Implémentation récursive des fonctions C++ : y a-t-il une limite à la profondeur de récursion ?

En C++, la récursivité est une technique puissante qui permet aux fonctions de s'appeler elles-mêmes. Cependant, il existe une limite à la profondeur de récursion, et le dépassement de cette limite provoque une erreur appelée débordement de pile.

Stack Overflow

Chaque appel de fonction pousse certaines données (telles que les paramètres de fonction, les variables locales et les adresses de retour) sur la pile. Lorsque la fonction reviendra, ces données seront extraites de la pile. Si la profondeur de récursion est trop grande, la pile peut être épuisée, provoquant une erreur de débordement de pile.

Limite de profondeur de récursion

C++ ne définit pas de valeur spécifique pour la limite de profondeur de récursion car elle dépend du système et du compilateur. Cependant, la limite peut généralement être considérée comme comprise entre 1 000 et 10 000.

Exemple pratique

Considérez la fonction récursive suivante pour calculer le nième terme de la séquence de Fibonacci :

int fib(int n) {
  if (n <= 1)
    return n;
  else
    return fib(n - 1) + fib(n - 2);
}

Si vous essayez de calculer fib(10000), cela provoquera un débordement de pile car la profondeur de récursion dépasse la limite.

Solution de contournement

Il existe plusieurs solutions de contournement pour résoudre le problème de limite de profondeur de récursion :

• Optimisation de la récursion de queue : Certains compilateurs peuvent optimiser les appels récursifs de queue, les convertissant en itérations, éliminant ainsi le besoin de la pile de récursivité. .
• Appel de queue : Convertissez manuellement l'appel récursif en un appel de queue, et attribuez des paramètres et renvoyez des valeurs à la fonction avant de revenir.
• Implémentation itérative : Réécrivez la fonction pour utiliser une boucle au lieu de la récursivité pour calculer le résultat.

Conclusion

La profondeur de récursion des fonctions C++ est limitée. Le dépassement de cette limite entraînera une erreur de débordement de pile. Cette limitation peut être contournée grâce à une optimisation récursive de fin, des appels de fin ou des implémentations itératives.

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!