当递归结果需用于其他计算时，如何将递归转换为迭代？

Great question! You’re spot-on that tail recursion is trivial to convert to iteration, but when recursive calls' results feed into further computations (i.e., non-tail recursion), we need to lean into how recursion works under the hood—by simulating the call stack manually. Here's a practical breakdown with examples:

Core Idea #

Recursion relies on the program's call stack to track two key things:

• The parameters of each recursive call
• The state of execution (whether we've already run child calls and need to process their results)

To convert this to iteration, we build our own stack to store this context, then process each "stack frame" explicitly.

Example 1: Fibonacci Sequence (Non-Tail Recursion) #

Let’s start with a classic non-tail recursive function, where we combine results from two child calls:

Recursive Implementation #

long fib(int n) {
    if (n <= 1) return n;
    // Recursive results are used in an addition—this is non-tail recursion
    return fib(n-1) + fib(n-2);
}

Iterative Conversion (Stack Simulation) #

We’ll use a stack to track each n we need to compute. When we hit a base case (n <=1), we add its value to our total. For non-base cases, we push the child calls onto the stack (in reverse order, since stacks are LIFO):

long fibIterative(int n) {
    Stack<Long> stack = new Stack<>();
    stack.push((long) n);
    long total = 0;

    while (!stack.isEmpty()) {
        long current = stack.pop();
        
        if (current <= 1) {
            total += current;
        } else {
            // Push n-2 first so n-1 is processed next (LIFO order)
            stack.push(current - 2);
            stack.push(current - 1);
        }
    }
    return total;
}

Example 2: Postorder Binary Tree Traversal #

Another common non-tail recursion scenario is tree traversal, where we process child nodes first before the parent:

Recursive Implementation #

void postorder(TreeNode root) {
    if (root == null) return;
    postorder(root.left);
    postorder(root.right);
    // Process node after child calls
    System.out.println(root.val);
}

Iterative Conversion (Stack with State Tracking) #

Here, we need to track whether we’ve already processed the node's children. We use a prev pointer to mark the last processed node:

void postorderIterative(TreeNode root) {
    Stack<TreeNode> stack = new Stack<>();
    TreeNode prev = null;
    TreeNode current = root;

    while (current != null || !stack.isEmpty()) {
        // Traverse to the leftmost node
        while (current != null) {
            stack.push(current);
            current = current.left;
        }

        current = stack.pop();
        // If right child is null or already processed, handle current node
        if (current.right == null || current.right == prev) {
            System.out.println(current.val);
            prev = current;
            current = null;
        } else {
            // Push current node back, then process right child
            stack.push(current);
            current = current.right;
        }
    }
}

General Steps for Conversion #

1. Identify Base Cases: These are the stopping points where you return a value without further recursion.
2. Define Stack Context: Decide what data to store in your stack (e.g., parameters, a flag indicating if child calls are complete).
3. Process Stack Frames:
   • For unprocessed frames: Push the current frame back (marked as processed), then push all child recursive calls (in reverse order to maintain execution order).
   • For processed frames: Execute the post-recursion logic (e.g., adding child results, processing a tree node).
4. Handle Base Cases: When you hit a base case, use its value as input for the parent frame's computation.

Key Takeaway #

While some non-tail recursive functions can be optimized with direct iteration (like Fibonacci's iterative formula), the stack-simulation approach works for all recursive functions—it’s the universal way to translate recursion to iteration when results need to be combined or processed further.

内容的提问来源于stack exchange，提问作者Kevin Cruijssen