Recursion is a powerful technique in computer science, often used for tasks like tree traversal, depth-first search, and backtracking algorithms. However, recursion can be less efficient in terms of both time and space due to the overhead of function calls and maintaining the call stack. In some cases, it’s beneficial to convert recursion to an iterative approach using an explicit stack to simulate the recursive calls. This article provides a step-by-step guide to converting recursive algorithms to iterative ones using a stack in JavaScript.
Why Convert Recursion to Iteration?
There are several reasons why you might want to convert recursion to iteration:
- Stack Overflow: Deep recursive calls can exhaust the call stack, leading to a stack overflow. Using an explicit stack can avoid this problem.
- Efficiency: Iterative solutions are generally more memory-efficient, as they do not require the overhead of maintaining the call stack.
- Better Control: Using an explicit stack can give you more control over the algorithm’s execution, especially when backtracking is involved.
Template for Converting Recursion to Iteration Using a Stack
When converting a recursive function to an iterative one using a stack, the general approach remains similar across different types of algorithms (like tree traversals, backtracking problems, or graph traversal). Below is a flexible template that can be adapted to various scenarios.
General Template
1. Recursive Function (Example)
function recursiveFunction(args) {
// Base case
if (baseCondition) {
// Handle the base case
return;
}
// Recursive calls
for (let i = 0; i < someLimit; i++) {
recursiveFunction(newArgs);
}
}
2. Iterative Function Using a Stack
To convert the above recursive function into an iterative one, we follow these steps:
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);
}
}
}
Template Breakdown
Initialize the Stack:
The stack should be initialized with the starting state, which could be the initial arguments or the first node in a traversal.Loop Through the Stack:
The loop continues as long as the stack has items, representing the recursive calls that would have been made in the original function.Base Condition Handling:
In recursion, the base condition checks if further recursion is necessary. In the iterative approach, you can perform the same check inside the loop. You may usecontinueto skip further processing when the base condition is met.Process the Current State:
Process the state of the current iteration (equivalent to the processing that would occur at the current recursive call).Push Next States:
Just like the recursive function calls new recursive functions, here you push the next states (i.e., function arguments or nodes to be processed) onto the stack.
Example Conversion: In-order Tree Traversal
Recursive Version:
function inorderTraversal(root) {
if (root === null) return;
inorderTraversal(root.left);
console.log(root.value);
inorderTraversal(root.right);
}
Iterative Version Using a Stack:
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;
}
}
Examples of Converting Recursion to Iteration
Example 1: Depth-First Search (DFS) on a Graph
Depth-First Search (DFS) is commonly implemented using recursion. Here's the recursive DFS algorithm:
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);
}
}
Iterative Version Using a Stack:
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);
}
}
}
}
In this example, the stack explicitly holds the nodes to be visited, and we use the loop to simulate the recursive calls.
Example 2: In-order Tree Traversal (Iterative)
In-order traversal of a binary tree is typically done recursively. Here's the recursive version:
function inorderTraversal(root) {
if (root === null) return;
inorderTraversal(root.left);
console.log(root.value);
inorderTraversal(root.right);
}
Iterative Version Using a Stack:
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;
}
}
In this case, the stack helps track nodes to be visited, and the inner loop traverses down the left side of the tree until reaching the leftmost node.
Example 3: Generating Subsets (Backtracking)
The backtracking approach for generating subsets of a set can be implemented recursively like this:
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;
}
Iterative Version Using a Stack:
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;
}
The iterative version uses a stack to simulate the recursive function calls. The currentSubset is modified in-place, and the stack handles backtracking by pushing new states onto it.
Example 4: Generating Permutations
To generate all permutations of a set, recursion is typically used:
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;
}
Iterative Version Using a Stack:
function permuteIterative(nums) {
let stack = [{start: 0, currentNums: [...nums]}];
let result = [];
while (stack.length > 0) {
let { start, currentNums } = stack.pop();
if (start === currentNums.length) {
result.push([...currentNums]);
continue;
}
for (let i = start; i < currentNums.length; i++) {
[currentNums[start], currentNums[i]] = [currentNums[i], currentNums[start]]; // swap
stack.push({start: start + 1, currentNums: [...currentNums]});
[currentNums[start], currentNums[i]] = [currentNums[i], currentNums[start]]; // backtrack (swap back)
}
}
return result;
}
This iterative version uses the stack to store the current state of the permutation. The backtracking is handled by pushing and popping the states from the stack.
Example 5: N-Queens Problem (Backtracking)
The N-Queens problem is often solved using recursive backtracking:
function solveNQueens(n) {
let result = [];
function backtrack(board, row) {
if (row === n) {
result.push(board.map(r => r.join('')));
return;
}
for (let col = 0; col < n; col++) {
if (isSafe(board, row, col)) {
board[row][col] = 'Q';
backtrack(board, row + 1);
board[row][col] = '.'; // backtrack
}
}
}
function isSafe(board, row, col) {
for (let i = 0; i < row; i++) {
if (board[i][col] === 'Q') return false;
if (col - (row - i) >= 0 && board[i][col - (row - i)] === 'Q') return false;
if (col + (row - i) < n && board[i][col + (row - i)] === 'Q') return false;
}
return true;
}
backtrack(Array.from({ length: n }, () => Array(n).fill('.')), 0);
return result;
}
Iterative Version Using a Stack:
function solveNQueensIterative(n) {
let stack = [{board: Array.from({ length: n }, () => Array(n).fill('.')), row: 0}];
let result = [];
while (stack.length > 0) {
let { board, row } = stack.pop();
if (row === n) {
result.push(board.map(r => r.join('')));
continue;
}
for (let col = 0; col < n; col++) {
if (isSafe(board, row, col)) {
board[row][col] = 'Q';
stack.push({ board: board.map(r => r.slice()), row: row + 1 });
board[row][col] = '.'; // backtrack
}
}
}
function isSafe(board, row, col) {
for (let i = 0; i < row; i++) {
if (board[i][col] === 'Q') return false;
if (col - (row - i) >= 0 && board[i][col - (row - i)] === 'Q') return false;
if (col + (row - i) < n && board[i][col + (row - i)] === 'Q') return false;
}
return true;
}
return result;
}
Conclusion
Converting recursion to iteration using a stack is a valuable technique for many algorithms, especially those involving backtracking or tree/graph traversal. By using an explicit stack, we can avoid deep recursion, manage function states manually, and ensure that we have better control over the algorithm’s execution. These examples should serve as a guide to help you tackle similar problems in your own code.
Top comments (0)