遞歸是電腦科學中的強大技術，通常用於樹遍歷、深度優先搜尋和回溯演算法等任務。然而，由於函數呼叫和維護呼叫堆疊的開銷，遞歸在時間和空間方面的效率可能較低。在某些情況下，使用顯式堆疊來模擬遞歸調用，將遞歸轉換為迭代方法是有益的。本文提供了在 JavaScript 中使用堆疊將遞歸演算法轉換為迭代演算法的逐步指南。
您可能想要將遞歸轉換為迭代的原因有幾個：
當使用堆疊將遞歸函數轉換為迭代函數時，不同類型的演算法（例如樹遍歷、回溯問題或圖遍歷）的一般方法保持相似。以下是一個靈活的模板，可以適應各種場景。
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);
}
}
}
初始化堆疊:
堆疊應使用起始狀態進行初始化，起始狀態可以是初始參數或遍歷中的第一個節點。
循環堆疊:
只要堆疊有項目，循環就會繼續，這表示在原始函數中進行的遞歸呼叫。
基本條件處理:
在遞歸中，基本條件檢查是否需要進一步遞歸。在迭代方法中，您可以在循環內執行相同的檢查。當滿足基本條件時，您可以使用繼續跳過進一步的處理。
處理目前狀態:
處理當前迭代的狀態（相當於當前遞歸呼叫時發生的處理）。
推送下一個狀態：
就像遞歸函數呼叫新的遞歸函數一樣，在這裡將下一個狀態（即要處理的函數參數或節點）推送到堆疊上。
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);
}
}
}
深度優先搜尋（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;
}
}
在這個例子中，堆疊明確地保存了要存取的節點，我們使用循環來模擬遞歸呼叫。
二元樹的中序遍歷通常是遞歸完成的。這是遞迴版本：
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);
}
}
}
}
在這種情況下，堆疊幫助追蹤要存取的節點，內循環向下遍歷樹的左側，直到到達最左邊的節點。
用於產生集合子集的回溯方法可以像這樣遞歸地實現：
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 被就地修改，堆疊透過將新狀態推送到其上來處理回溯。
要產生集合的所有排列，通常使用遞歸：
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;
}
這個迭代版本使用堆疊來儲存排列的目前狀態。回溯是透過從堆疊中壓入和彈出狀態來處理的。
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);
}
}
使用堆疊將遞歸轉換為迭代對於許多演算法來說是一項很有價值的技術，特別是那些涉及回溯或樹/圖遍歷的演算法。透過使用顯式堆疊，我們可以避免深度遞歸，手動管理函數狀態，並確保我們更好地控制演算法的執行。這些範例應該作為指南來幫助您解決自己程式碼中的類似問題。
以上是使用堆疊將遞歸轉換為迭代：實用指南的詳細內容。更多資訊請關注PHP中文網其他相關文章！
