Conversion de la récursion en itération à l'aide d'une pile : un guide pratique

La récursion est une technique puissante en informatique, souvent utilisée pour des tâches telles que la traversée d'arbres, la recherche en profondeur d'abord et les algorithmes de retour en arrière. Cependant, la récursion peut être moins efficace en termes de temps et d'espace en raison de la surcharge des appels de fonction et de la maintenance de la pile d'appels. Dans certains cas, il est avantageux de convertir la récursivité en une approche itérative utilisant une pile explicite pour simuler les appels récursifs. Cet article fournit un guide étape par étape pour convertir des algorithmes récursifs en algorithmes itératifs à l'aide d'une pile en JavaScript.

---

Pourquoi convertir la récursivité en itération ?

Il existe plusieurs raisons pour lesquelles vous souhaiterez peut-être convertir la récursivité en itération :

1. Stack Overflow : des appels récursifs profonds peuvent épuiser la pile d'appels, entraînant un débordement de pile. L'utilisation d'une pile explicite peut éviter ce problème.
2. Efficacité : les solutions itératives sont généralement plus efficaces en termes de mémoire, car elles ne nécessitent pas de frais généraux liés à la maintenance de la pile d'appels.
3. Meilleur contrôle : L'utilisation d'une pile explicite peut vous donner plus de contrôle sur l'exécution de l'algorithme, en particulier lorsqu'un retour en arrière est impliqué.

---

Modèle pour convertir la récursion en itération à l'aide d'une pile

Lors de la conversion d'une fonction récursive en fonction itérative à l'aide d'une pile, l'approche générale reste similaire pour différents types d'algorithmes (comme les parcours d'arbres, les problèmes de retour en arrière ou le parcours de graphiques). Vous trouverez ci-dessous un modèle flexible qui peut être adapté à différents scénarios.

---

Modèle général

1. Fonction récursive (exemple)

function recursiveFunction(args) {
    // Base case
    if (baseCondition) {
        // Handle the base case
        return;
    }

    // Recursive calls
    for (let i = 0; i < someLimit; i++) {
        recursiveFunction(newArgs);
    }
}

2. Fonction itérative utilisant une pile

Pour convertir la fonction récursive ci-dessus en une fonction itérative, nous suivons ces étapes :

function iterativeFunction(args) {
    // Initialize the stack
    let stack = [initialState];

    // Loop until the stack is empty
    while (stack.length > 0) {
        // Pop the current state from the stack
        let currentState = stack.pop();

        // Handle the base case (optional, since we can check on each iteration)
        if (baseCondition) {
            continue;  // Skip or handle the base case
        }

        // Process the current state
        processState(currentState);

        // Push next states onto the stack
        for (let i = 0; i < someLimit; i++) {
            let newState = generateNewState(currentState, i);
            stack.push(newState);
        }
    }
}

---

Répartition du modèle

1. Initialiser la pile :
   
   La pile doit être initialisée avec l'état de départ, qui peut être les arguments initiaux ou le premier nœud d'un parcours.

2. Boucle à travers la pile :
   
   La boucle continue tant que la pile contient des éléments, représentant les appels récursifs qui auraient été effectués dans la fonction d'origine.

3. Gestion des conditions de base :
   
   En récursivité, la condition de base vérifie si une récursivité supplémentaire est nécessaire. Dans l’approche itérative, vous pouvez effectuer la même vérification à l’intérieur de la boucle. Vous pouvez utiliser Continuer pour ignorer la suite du traitement lorsque la condition de base est remplie.

4. Traiter l'état actuel :
   
   Traite l'état de l'itération en cours (équivalent au traitement qui se produirait lors de l'appel récursif en cours).

5. Pousser les états suivants :
   
   Tout comme la fonction récursive appelle de nouvelles fonctions récursives, ici vous poussez les états suivants (c'est-à-dire les arguments de fonction ou les nœuds à traiter) sur la pile.

---

Exemple de conversion : parcours d'arbre dans l'ordre

Version récursive :

function recursiveFunction(args) {
    // Base case
    if (baseCondition) {
        // Handle the base case
        return;
    }

    // Recursive calls
    for (let i = 0; i < someLimit; i++) {
        recursiveFunction(newArgs);
    }
}

Version itérative utilisant une pile :

function iterativeFunction(args) {
    // Initialize the stack
    let stack = [initialState];

    // Loop until the stack is empty
    while (stack.length > 0) {
        // Pop the current state from the stack
        let currentState = stack.pop();

        // Handle the base case (optional, since we can check on each iteration)
        if (baseCondition) {
            continue;  // Skip or handle the base case
        }

        // Process the current state
        processState(currentState);

        // Push next states onto the stack
        for (let i = 0; i < someLimit; i++) {
            let newState = generateNewState(currentState, i);
            stack.push(newState);
        }
    }
}

---

Exemples de conversion de récursivité en itération

Exemple 1 : Recherche en profondeur d'abord (DFS) sur un graphique

La recherche en profondeur (DFS) est couramment mise en œuvre à l'aide de la récursivité. Voici l'algorithme DFS récursif :

function inorderTraversal(root) {
    if (root === null) return;
    inorderTraversal(root.left);
    console.log(root.value);
    inorderTraversal(root.right);
}

Version itérative utilisant une pile :

function inorderTraversalIterative(root) {
    let stack = [];
    let current = root;

    while (stack.length > 0 || current !== null) {
        // Reach the leftmost node
        while (current !== null) {
            stack.push(current);
            current = current.left;
        }

        // Visit the node
        current = stack.pop();
        console.log(current.value);

        // Move to the right node
        current = current.right;
    }
}

Dans cet exemple, la pile contient explicitement les nœuds à visiter, et nous utilisons la boucle pour simuler les appels récursifs.

---

Exemple 2 : Parcours d'arbre dans l'ordre (itératif)

Le parcours dans l'ordre d'un arbre binaire est généralement effectué de manière récursive. Voici la version récursive :

function dfs(graph, node, visited = new Set()) {
    if (visited.has(node)) return;
    console.log(node);
    visited.add(node);

    for (let neighbor of graph[node]) {
        dfs(graph, neighbor, visited);
    }
}

Version itérative utilisant une pile :

function dfsIterative(graph, startNode) {
    let stack = [startNode];
    let visited = new Set();

    while (stack.length > 0) {
        let node = stack.pop();

        if (visited.has(node)) continue;

        console.log(node);
        visited.add(node);

        // Add neighbors to the stack in reverse order to maintain DFS order
        for (let neighbor of graph[node].reverse()) {
            if (!visited.has(neighbor)) {
                stack.push(neighbor);
            }
        }
    }
}

Dans ce cas, la pile aide à suivre les nœuds à visiter, et la boucle interne parcourt le côté gauche de l'arborescence jusqu'à atteindre le nœud le plus à gauche.

---

Exemple 3 : génération de sous-ensembles (retour en arrière)

L'approche de backtracking pour générer des sous-ensembles d'un ensemble peut être implémentée de manière récursive comme ceci :

function inorderTraversal(root) {
    if (root === null) return;
    inorderTraversal(root.left);
    console.log(root.value);
    inorderTraversal(root.right);
}

Version itérative utilisant une pile :

function inorderTraversalIterative(root) {
    let stack = [];
    let current = root;

    while (stack.length > 0 || current !== null) {
        // Reach the leftmost node
        while (current !== null) {
            stack.push(current);
            current = current.left;
        }

        // Visit the node
        current = stack.pop();
        console.log(current.value);

        // Move to the right node
        current = current.right;
    }
}

La version itérative utilise une pile pour simuler les appels de fonctions récursifs. Le currentSubset est modifié sur place et la pile gère le retour en arrière en y insérant de nouveaux états.

---

Exemple 4 : Générer des permutations

Pour générer toutes les permutations d'un ensemble, la récursivité est généralement utilisée :

function subsets(nums) {
    let result = [];
    function backtrack(start, currentSubset) {
        result.push([...currentSubset]);
        for (let i = start; i < nums.length; i++) {
            currentSubset.push(nums[i]);
            backtrack(i + 1, currentSubset);
            currentSubset.pop();
        }
    }
    backtrack(0, []);
    return result;
}

Version itérative utilisant une pile :

function subsetsIterative(nums) {
    let stack = [{start: 0, currentSubset: []}];
    let result = [];

    while (stack.length > 0) {
        let { start, currentSubset } = stack.pop();
        result.push([...currentSubset]);

        // Explore subsets by including elements from `start` onwards
        for (let i = start; i < nums.length; i++) {
            currentSubset.push(nums[i]);
            stack.push({ start: i + 1, currentSubset: [...currentSubset] });
            currentSubset.pop(); // backtrack
        }
    }

    return result;
}

Cette version itérative utilise la pile pour stocker l'état actuel de la permutation. Le retour en arrière est géré en poussant et en supprimant les états de la pile.

---

Exemple 5 : Problème N-Queens (retour en arrière)

Le problème des N-Queens est souvent résolu en utilisant le backtracking récursif :

function permute(nums) {
    let result = [];
    function backtrack(start) {
        if (start === nums.length) {
            result.push([...nums]);
            return;
        }
        for (let i = start; i < nums.length; i++) {
            [nums[start], nums[i]] = [nums[i], nums[start]];  // swap
            backtrack(start + 1);
            [nums[start], nums[i]] = [nums[i], nums[start]];  // backtrack (swap back)
        }
    }
    backtrack(0);
    return result;
}

Version itérative utilisant une pile :

function recursiveFunction(args) {
    // Base case
    if (baseCondition) {
        // Handle the base case
        return;
    }

    // Recursive calls
    for (let i = 0; i < someLimit; i++) {
        recursiveFunction(newArgs);
    }
}

---

Conclusion

La conversion de la récursion en itération à l'aide d'une pile est une technique précieuse pour de nombreux algorithmes, en particulier ceux impliquant un retour en arrière ou une traversée d'arbres/graphes. En utilisant une pile explicite, nous pouvons éviter une récursion profonde, gérer manuellement les états des fonctions et garantir un meilleur contrôle sur l’exécution de l’algorithme. Ces exemples devraient servir de guide pour vous aider à résoudre des problèmes similaires dans votre propre code.

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!