Comment résoudre le problème de débordement de pile des fonctions récursives C++ ?

Pour le problème de débordement de pile des fonctions récursives C++, les solutions incluent : la réduction de la profondeur de récursion, la réduction de la taille du cadre de pile et l'optimisation de la récursion de queue. Par exemple, la fonction de séquence de Fibonacci peut éviter le débordement de pile grâce à l'optimisation de la récursion de queue.

Comment résoudre le problème de débordement de pile des fonctions récursives en C++ ?

Raison

Les fonctions récursives créent de nouveaux cadres de pile sur la pile à chaque fois qu'elles sont appelées. Lorsque la profondeur de récursion est trop grande et que l'espace de pile est insuffisant, un débordement de pile se produit.

Solution

1. Réduisez la profondeur de récursion

• Recherchez des algorithmes non récursifs qui remplacent la récursion, tels que la méthode d'itération ou de mémo.
• Divisez les appels récursifs et réduisez la profondeur de récursion.

2. Réduisez la taille du cadre de pile

• Utilisez des variables locales au lieu de variables membres pour réduire la taille du cadre de pile.
• Utilisez la transmission de valeur au lieu de la transmission de référence pour éviter les copies redondantes.

3. Optimisation de la récursion de queue

• Lorsque le dernier appel d'une fonction récursive est récursif de queue (c'est-à-dire que la fonction n'effectue aucune autre opération et s'appelle directement), le compilateur peut effectuer une optimisation récursive de queue. Cela élimine les trames de pile requises pour les appels récursifs, résolvant ainsi efficacement le problème de débordement de pile.

Exemple pratique

Considérez la fonction de séquence de Fibonacci suivante :

// 尾递归版本
int fibonacci(int n) {
  return fibonacci_helper(n, 0, 1);
}

int fibonacci_helper(int n, int a, int b) {
  if (n == 0) return a;
  return fibonacci_helper(n-1, b, a+b);
}

Il s'agit de la version récursive de queue, car le dernier appel de fonction est directement récursif sur lui-même. Le compilateur l'optimisera pour éviter le débordement de pile.

Ce qui suit est la version récursive sans queue :

int fibonacci(int n) {
  if (n == 0) return 0;
  if (n == 1) return 1;
  return fibonacci(n-1) + fibonacci(n-2);
}

Pour cette version récursive sans queue, vous pouvez utiliser des techniques d'optimisation récursive de queue pour la convertir en une version récursive de queue. Par exemple, en utilisant des fonctions auxiliaires et des opérations d'échange :

int fibonacci(int n, int a = 0, int b = 1) {
  if (n == 0) return a;
  if (n == 1) return b;
  // 进行 swap 操作
  std::swap(a, b);
  return fibonacci(n-1, b, a+b);
}

En utilisant l'optimisation de la récursion de queue ou en réduisant la profondeur de récursion, le problème de débordement de pile des fonctions récursives en C++ peut être résolu efficacement.

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!