Maison > développement back-end > C++ > le corps du texte

Erreur de compilation C++ : une récursivité trop profonde provoque un débordement de pile. Comment le résoudre ?

WBOY
Libérer: 2023-08-22 16:07:46
original
2624 Les gens l'ont consulté

Erreur de compilation C++ : une récursivité trop profonde provoque un débordement de pile. Comment le résoudre ?

C++ est un langage de programmation largement utilisé, et il est inévitable de rencontrer diverses erreurs lors de sa compilation et de son exécution. Une erreur courante consiste à effectuer une récursivité trop profonde et à provoquer un débordement de pile.

En récursivité, lorsqu'il y a trop de niveaux de récursion, le programme rencontrera des erreurs de dépassement de pile. En effet, les fonctions récursives nécessitent une certaine quantité d'espace mémoire pour stocker les variables locales et les appels de fonction lors de chaque récursivité. Chaque récursion poussera ces variables locales et appels de fonction dans la pile d'appels de fonction. La taille de la pile est limitée. Une fois cette limite dépassée, un débordement de pile se produira, provoquant le crash du programme.

Alors, comment devrions-nous résoudre le débordement de pile causé par une récursion trop profonde ? Voici plusieurs solutions.

  1. Réécrire la récursion dans une boucle

L'essence d'une fonction récursive est une boucle avec retour en arrière, donc sans affecter la logique du programme, nous pouvons réécrire la fonction récursive dans une boucle. Cela peut réduire la surcharge causée par la récursivité, réduisant ainsi le risque de débordement de pile.

Par exemple, ce qui suit est une fonction récursive qui calcule la séquence de Fibonacci :

int fib(int n) {
    if (n == 0 || n == 1) {
        return n;
    }
    return fib(n - 1) + fib(n - 2);
}
Copier après la connexion
Copier après la connexion

Nous pouvons la réécrire sous la forme de boucle suivante :

int fib(int n) {
    if (n == 0 || n == 1) {
        return n;
    }
    int a = 0, b = 1;
    for (int i = 2; i <= n; i++) {
        int c = a + b;
        a = b;
        b = c;
    }
    return b;
}
Copier après la connexion
  1. Augmentez l'espace de la pile

Nous pouvons éviter cela en définissant la taille de l'espace de pile Débordement de pile. Sous Windows, cela peut être réalisé en modifiant la taille de l'espace de pile du fichier exécutable du programme ; sous Linux, vous pouvez utiliser la commande ulimit pour contrôler la taille de la pile. Une chose à noter avec cette approche est que trop d’espace de pile occupera des ressources système, vous devez donc peser le pour et le contre.

  1. Ajustez l'algorithme récursif

Parfois, l'algorithme récursif lui-même peut avoir des problèmes, entraînant trop de niveaux de récursivité. Dans ce cas, nous devons optimiser l'algorithme récursif et réduire le nombre d'appels récursifs pour réduire le risque de débordement de pile.

Par exemple, voici un algorithme récursif pour résoudre la séquence de Fibonacci :

int fib(int n) {
    if (n == 0 || n == 1) {
        return n;
    }
    return fib(n - 1) + fib(n - 2);
}
Copier après la connexion
Copier après la connexion

Nous pouvons optimiser cet algorithme grâce à une recherche mémorisée pour réduire le nombre d'appels récursifs :

int fib(int n, unordered_map<int, int>& memo) {
    if (n == 0 || n == 1) {
        return n;
    }
    if (memo.find(n) != memo.end()) {
        return memo[n];
    }
    int ans = fib(n - 1, memo) + fib(n - 2, memo);
    memo[n] = ans;
    return ans;
}

int fib(int n) {
    unordered_map<int, int> memo;
    return fib(n, memo);
}
Copier après la connexion
  1. Éviter les calculs répétés de fonctions récursives

Dans fonctions récursives, il peut y avoir des sous-problèmes de calculs répétés. Nous pouvons éviter cela en utilisant un mécanisme de mise en cache pour réduire le nombre d'appels récursifs.

Par exemple, si nous devons calculer un nombre catalan, nous pouvons utiliser le mécanisme de mise en cache pour éviter des calculs répétés :

int catalan(int n, unordered_map<int, int>& memo) {
    if (n <= 1) {
        return 1;
    }
    if (memo.find(n) != memo.end()) {
        return memo[n];
    }
    int ans = 0;
    for (int i = 0; i < n; i++) {
        ans += catalan(i, memo) * catalan(n - 1 - i, memo);
    }
    memo[n] = ans;
    return ans;
}

int catalan(int n) {
    unordered_map<int, int> memo;
    return catalan(n, memo);
}
Copier après la connexion

En bref, il existe de nombreuses façons d'éviter un débordement de pile causé par une récursivité trop profonde, et nous devons choisir la méthode appropriée en fonction de la situation spécifique. Lors de l'écriture de fonctions récursives, veillez à faire attention à la profondeur de la récursion et testez entièrement pour vous assurer que le programme fonctionne correctement.

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!

source:php.cn
Déclaration de ce site Web
Le contenu de cet article est volontairement contribué par les internautes et les droits d'auteur appartiennent à l'auteur original. Ce site n'assume aucune responsabilité légale correspondante. Si vous trouvez un contenu suspecté de plagiat ou de contrefaçon, veuillez contacter admin@php.cn
Tutoriels populaires
Plus>
Derniers téléchargements
Plus>
effets Web
Code source du site Web
Matériel du site Web
Modèle frontal