遞歸是電腦科學中的強大技術，通常用於樹遍歷、深度優(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中文網其他相關文章！