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

---

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

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

1. 堆疊溢位：深度遞歸呼叫可能會(huì)耗盡呼叫堆疊，導(dǎo)致堆疊溢位。使用顯式堆疊可以避免這個(gè)問(wèn)題。
2. 效率：迭代解決方案通常更節(jié)省內(nèi)存，因?yàn)樗鼈儾恍枰S護(hù)呼叫堆疊的開(kāi)銷(xiāo)。
3. 更好的控制：使用顯式堆疊可以讓您更好地控制演算法的執(zhí)行，特別是在涉及回溯時(shí)。

---

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

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

---

通用模板

1. 遞歸函數(shù)（範(fàn)例）

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)行的遞歸呼叫。

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

4. 處理目前狀態(tài):
   
   處理當(dāng)前迭代的狀態(tài)（相當(dāng)於當(dāng)前遞歸呼叫時(shí)發(fā)生的處理）。

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

---

轉(zhuǎn)換範(fàn)例：有序樹(shù)遍歷

遞迴版本：

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)換為迭代的範(fàn)例

範(fàn)例 1：圖上的深度優(yōu)先搜尋 (DFS)

深度優(yōu)先搜尋（DFS）通常使用遞歸來(lái)實(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)來(lái)模擬遞歸呼叫。

---

範(fàn)例2：中序樹(shù)遍歷（迭代）

二元樹(shù)的中序遍歷通常是遞歸完成的。這是遞迴版本：

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)向下遍歷樹(shù)的左側(cè)，直到到達(dá)最左邊的節(jié)點(diǎn)。

---

範(fàn)例 3：產(chǎn)生子集（回溯）

用於產(chǎn)生集合子集的回溯方法可以像這樣遞歸地實(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;
    }
}

迭代版本使用堆疊來(lái)模擬遞歸函數(shù)呼叫。 currentSubset 被就地修改，堆疊透過(guò)將新?tīng)顟B(tài)推送到其上來(lái)處理回溯。

---

範(fàn)例 4：生成排列

要產(chǎn)生集合的所有排列，通常使用遞歸：

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è)迭代版本使用堆疊來(lái)儲(chǔ)存排列的目前狀態(tài)?；厮菔峭高^(guò)從堆疊中壓入和彈出狀態(tài)來(lái)處理的。

---

例 5：N 皇后問(wèn)題（回溯）

N 皇后問(wèn)題通常使用遞歸回溯來(lái)解決：

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ì)於許多演算法來(lái)說(shuō)是一項(xiàng)很有價(jià)值的技術(shù)，特別是那些涉及回溯或樹(shù)/圖遍歷的演算法。透過(guò)使用顯式堆疊，我們可以避免深度遞歸，手動(dòng)管理函數(shù)狀態(tài)，並確保我們更好地控制演算法的執(zhí)行。這些範(fàn)例應(yīng)該作為指南來(lái)幫助您解決自己程式碼中的類(lèi)似問(wèn)題。

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