递归是计算机科学中的一项强大技术，通常用于树遍历、深度优先搜索和回溯算法等任务。然而，由于函数调用和维护调用堆栈的开销，递归在时间和空间方面的效率可能较低。在某些情况下，使用显式堆栈来模拟递归调用，将递归转换为迭代方法是有益的。本文提供了在 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中文网其他相关文章！
