遞歸是計(jì)算機(jī)科學(xué)中的一項(xiàng)強(qiáng)大技術(shù)，通常用于樹遍歷、深度優(yōu)先搜索和回溯算法等任務(wù)。然而，由于函數(shù)調(diào)用和維護(hù)調(diào)用堆棧的開銷，遞歸在時(shí)間和空間方面的效率可能較低。在某些情況下，使用顯式堆棧來模擬遞歸調(diào)用，將遞歸轉(zhuǎn)換為迭代方法是有益的。本文提供了在 JavaScript 中使用堆棧將遞歸算法轉(zhuǎn)換為迭代算法的分步指南。

---

為什么將遞歸轉(zhuǎn)換為迭代？

您可能想要將遞歸轉(zhuǎn)換為迭代的原因有幾個(gè)：

1. 堆棧溢出：深度遞歸調(diào)用可能耗盡調(diào)用堆棧，導(dǎo)致堆棧溢出。使用顯式堆?？梢员苊膺@個(gè)問題。
2. 效率：迭代解決方案通常更節(jié)省內(nèi)存，因?yàn)樗鼈儾恍枰S護(hù)調(diào)用堆棧的開銷。
3. 更好的控制：使用顯式堆?？梢宰屇玫乜刂扑惴ǖ膱?zhí)行，特別是在涉及回溯時(shí)。

---

使用堆棧將遞歸轉(zhuǎn)換為迭代的模板

當(dāng)使用堆棧將遞歸函數(shù)轉(zhuǎn)換為迭代函數(shù)時(shí)，不同類型的算法（例如樹遍歷、回溯問題或圖遍歷）的一般方法保持相似。下面是一個(gè)靈活的模板，可以適應(yīng)各種場(chǎng)景。

---

通用模板

1. 遞歸函數(shù)（示例）

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

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

2. 使用堆棧的迭代函數(shù)

要將上述遞歸函數(shù)轉(zhuǎn)換為迭代函數(shù)，我們按照以下步驟操作：

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

---

模板分解

1. 初始化堆棧:
   
   堆棧應(yīng)使用起始狀態(tài)進(jìn)行初始化，起始狀態(tài)可以是初始參數(shù)或遍歷中的第一個(gè)節(jié)點(diǎn)。

2. 循環(huán)堆棧:
   
   只要堆棧有項(xiàng)目，循環(huán)就會(huì)繼續(xù)，這表示在原始函數(shù)中進(jìn)行的遞歸調(diào)用。

3. 基本條件處理:
   
   在遞歸中，基本條件檢查是否需要進(jìn)一步遞歸。在迭代方法中，您可以在循環(huán)內(nèi)執(zhí)行相同的檢查。當(dāng)滿足基本條件時(shí)，您可以使用繼續(xù)跳過進(jìn)一步的處理。

4. 處理當(dāng)前狀態(tài):
   
   處理當(dāng)前迭代的狀態(tài)（相當(dāng)于當(dāng)前遞歸調(diào)用時(shí)發(fā)生的處理）。

5. 推送下一個(gè)狀態(tài)：
   
   就像遞歸函數(shù)調(diào)用新的遞歸函數(shù)一樣，在這里將下一個(gè)狀態(tài)（即要處理的函數(shù)參數(shù)或節(jié)點(diǎn)）推送到堆棧上。

---

轉(zhuǎn)換示例：有序樹遍歷

遞歸版本：

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

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

使用堆棧的迭代版本：

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

---

將遞歸轉(zhuǎn)換為迭代的示例

示例 1：圖上的深度優(yōu)先搜索 (DFS)

深度優(yōu)先搜索（DFS）通常使用遞歸來實(shí)現(xiàn)。這是遞歸 DFS 算法：

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

使用堆棧的迭代版本:

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

在這個(gè)例子中，堆棧顯式地保存了要訪問的節(jié)點(diǎn)，我們使用循環(huán)來模擬遞歸調(diào)用。

---

示例2：中序樹遍歷（迭代）

二叉樹的中序遍歷通常是遞歸完成的。這是遞歸版本：

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

使用堆棧的迭代版本:

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

在這種情況下，堆棧幫助跟蹤要訪問的節(jié)點(diǎn)，內(nèi)循環(huán)向下遍歷樹的左側(cè)，直到到達(dá)最左邊的節(jié)點(diǎn)。

---

示例 3：生成子集（回溯）

用于生成集合子集的回溯方法可以像這樣遞歸地實(shí)現(xiàn)：

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

使用堆棧的迭代版本:

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

迭代版本使用堆棧來模擬遞歸函數(shù)調(diào)用。 currentSubset 被就地修改，堆棧通過將新狀態(tài)推送到其上來處理回溯。

---

示例 4：生成排列

要生成集合的所有排列，通常使用遞歸：

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

使用堆棧的迭代版本:

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

這個(gè)迭代版本使用堆棧來存儲(chǔ)排列的當(dāng)前狀態(tài)?；厮菔峭ㄟ^從堆棧中壓入和彈出狀態(tài)來處理的。

---

示例 5：N 皇后問題（回溯）

N 皇后問題通常使用遞歸回溯來解決：

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

使用堆棧的迭代版本:

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

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

---

結(jié)論

使用堆棧將遞歸轉(zhuǎn)換為迭代對(duì)于許多算法來說是一項(xiàng)很有價(jià)值的技術(shù)，特別是那些涉及回溯或樹/圖遍歷的算法。通過使用顯式堆棧，我們可以避免深度遞歸，手動(dòng)管理函數(shù)狀態(tài)，并確保我們更好地控制算法的執(zhí)行。這些示例應(yīng)該作為指南來幫助您解決自己代碼中的類似問題。

以上是使用堆棧將遞歸轉(zhuǎn)換為迭代：實(shí)用指南的詳細(xì)內(nèi)容。更多信息請(qǐng)關(guān)注PHP中文網(wǎng)其他相關(guān)文章！