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:

1. Stack Overflow: Deep recursive calls can exhaust the call stack, leading to a stack overflow. Using an explicit stack can avoid this problem.
2. Efficiency: Iterative solutions are generally more memory-efficient, as they do not require the overhead of maintaining the call stack.
3. 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

1. 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.

2. 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.

3. 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 use continue to skip further processing when the base condition is met.

4. Process the Current State:
   
   Process the state of the current iteration (equivalent to the processing that would occur at the current recursive call).

5. 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 recursiveFunction(args) {
    // Base case
    if (baseCondition) {
        // Handle the base case
        return;
    }

    // Recursive calls
    for (let i = 0; i < someLimit; i++) {
        recursiveFunction(newArgs);
    }
}

Iterative Version Using a Stack:

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);
        }
    }
}

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 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 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 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 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 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;
    }
}

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 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;
}

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 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 recursiveFunction(args) {
    // Base case
    if (baseCondition) {
        // Handle the base case
        return;
    }

    // Recursive calls
    for (let i = 0; i < someLimit; i++) {
        recursiveFunction(newArgs);
    }
}

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.

The above is the detailed content of Converting Recursion to Iteration Using a Stack: A Practical Guide. For more information, please follow other related articles on the PHP Chinese website!