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

---

為什么將遞歸轉換為迭代？

您可能想要將遞歸轉換為迭代的原因有幾個：

1. 堆棧溢出：深度遞歸調用可能耗盡調用堆棧，導致堆棧溢出。使用顯式堆棧可以避免這個問題。
2. 效率：迭代解決方案通常更節(jié)省內存，因為它們不需要維護調用堆棧的開銷。
3. 更好的控制：使用顯式堆?？梢宰屇玫乜刂扑惴ǖ膱?zhí)行，特別是在涉及回溯時。

---

使用堆棧將遞歸轉換為迭代的模板

當使用堆棧將遞歸函數轉換為迭代函數時，不同類型的算法（例如樹遍歷、回溯問題或圖遍歷）的一般方法保持相似。下面是一個靈活的模板，可以適應各種場景。

---

通用模板

1. 遞歸函數（示例）

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

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

2. 使用堆棧的迭代函數

要將上述遞歸函數轉換為迭代函數，我們按照以下步驟操作：

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. 初始化堆棧:
   
   堆棧應使用起始狀態(tài)進行初始化，起始狀態(tài)可以是初始參數或遍歷中的第一個節(jié)點。

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

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

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

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

---

轉換示例：有序樹遍歷

遞歸版本：

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

---

將遞歸轉換為迭代的示例

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

深度優(yōu)先搜索（DFS）通常使用遞歸來實現。這是遞歸 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;
    }
}

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

---

示例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é)點，內循環(huán)向下遍歷樹的左側，直到到達最左邊的節(jié)點。

---

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

用于生成集合子集的回溯方法可以像這樣遞歸地實現：

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

迭代版本使用堆棧來模擬遞歸函數調用。 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;
}

這個迭代版本使用堆棧來存儲排列的當前狀態(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);
    }
}

---

結論

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

以上是使用堆棧將遞歸轉換為迭代：實用指南的詳細內容。更多信息請關注PHP中文網其他相關文章！