如何用自定义Stack将含循环的递归回溯转为非递归形式（Java）

最近一直在折腾递归转非递归的实现，分享下我踩过的坑和最终的解决思路：

• 基础实现已搞定：我用Java写了自定义Stack的通用方法，已经能把像中序遍历（Inorder-Traversal）这种没有循环的递归转成非递归形式。核心思路是用栈模拟递归调用栈，再加个state变量标记后续要执行的代码位置（毕竟Java没法用GOTO），这个逻辑理解起来挺顺畅的。

• 遇到的瓶颈：碰到回溯类问题比如子集问题时直接卡壳了——这类递归里存在循环嵌套递归调用，完全不知道怎么用自定义Stack来对应这种逻辑。查了不少资料，要么用到Java不支持的GOTO关键字，要么只针对无嵌套、无循环的简单递归场景，根本解决不了我的问题。

• 通宵搞定的解决方案：后来花了一整晚死磕这个问题，终于写出了纯用自定义Stack实现的非递归子集问题代码，注释里把思路写得明明白白。其实核心就是把循环和栈操作结合起来，用条件判断处理递归里的循环逻辑——之前卡壳就是没搞清楚怎么把递归中的循环和栈的状态管理结合起来，现在发现只要在栈里保存每次递归调用的「上下文」（比如当前遍历的起始索引、已选择的元素集合等），就能完美模拟回溯的过程。

举个我写的Java代码示例：

import java.util.*;

public class SubsetNonRecursive {
    public static List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        // 栈中存储递归调用的上下文：当前处理的起始索引、已选择的元素路径
        Stack<Object[]> callStack = new Stack<>();
        // 初始状态：从索引0开始，空元素路径
        callStack.push(new Object[]{0, new ArrayList<Integer>()});

        while (!callStack.isEmpty()) {
            Object[] currentCtx = callStack.pop();
            int currentIndex = (int) currentCtx[0];
            List<Integer> currentPath = (List<Integer>) currentCtx[1];

            // 对应递归中先收集当前路径的逻辑
            result.add(new ArrayList<>(currentPath));

            // 模拟递归里的循环：从当前索引遍历后续元素
            for (int i = currentIndex; i < nums.length; i++) {
                // 选择当前元素，生成新的路径
                List<Integer> newPath = new ArrayList<>(currentPath);
                newPath.add(nums[i]);
                // 将新的调用上下文压入栈：下一个起始索引为i+1，携带新路径
                callStack.push(new Object[]{i + 1, newPath});
            }
        }
        return result;
    }

    public static void main(String[] args) {
        int[] testNums = {1, 2, 3};
        System.out.println(subsets(testNums));
    }
}

关键思路解释： #

栈里保存的是每次递归调用的完整上下文，包括当前要处理的数组起始索引，以及已经选好的元素路径。每次弹出栈顶元素时：

1. 先把当前路径加入结果集，对应递归函数中进入后先收集结果的逻辑；
2. 然后遍历从当前索引开始的后续元素，把「选择该元素后的新路径+下一个起始索引」作为新的上下文压入栈，这就模拟了递归中「选当前元素，然后递归处理剩余元素」的过程。
   栈的后进先出特性刚好对应递归调用的顺序，完美复刻了回溯的逻辑。

总结 #

回溯类递归转非递归的核心，就是把递归中每次调用的上下文状态都妥善保存到栈里，配合循环来模拟递归中的迭代过程，完全不需要依赖GOTO。之前卡壳就是没摸透这层逻辑，理清之后发现其实没那么复杂～

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