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);
}

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;
}

2. 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.

3. 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);
}

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);
}

4. É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);
}

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!