如何将含多个递归调用的递归函数转为迭代？已掌握单递归转换方法

当递归函数包含多个递归调用时，核心是手动模拟调用栈的执行状态——递归本身会通过调用栈自动跟踪每个函数的执行进度，我们要做的就是把这个“进度跟踪”显式写出来，给每个栈元素加上状态标记，记录当前节点已经完成了哪些子调用，还剩哪些待执行。

先回顾你的单个递归转换思路 #

你已经掌握的单个递归转迭代，本质是把所有需要后续处理的节点先压栈，等所有前置递归执行完，再批量处理doStuff。但多递归调用的场景下，每个节点的处理是分阶段的，不能一次性压完所有节点，必须跟踪阶段。

多递归调用的转换方案（以你给出的函数为例） #

原始递归函数：

function f(n){
    if(n>0){
        f(n-1);
        f(n-2);
        doStuff(n);
    }
}

迭代版本的关键是给每个栈元素添加状态标记，这里我们用state字段区分三个阶段：

• state: 0：刚进入当前节点，还未执行任何子递归，需要先执行f(n-1)
• state: 1：已经执行完f(n-1)，接下来要执行f(n-2)
• state: 2：已经执行完所有子递归，现在可以执行doStuff(n)

对应的迭代实现：

function f(n) {
    const stack = [{ n: n, state: 0 }];
    
    while (stack.length > 0) {
        const current = stack.pop();
        const { n: currentN, state } = current;
        
        if (currentN <= 0) {
            continue; // 递归终止条件，直接跳过
        }
        
        switch (state) {
            case 0:
                // 阶段0：先把当前节点（状态改为1）压回栈，再压入f(n-1)的初始状态
                stack.push({ n: currentN, state: 1 });
                stack.push({ n: currentN - 1, state: 0 });
                break;
            case 1:
                // 阶段1：把当前节点（状态改为2）压回栈，再压入f(n-2)的初始状态
                stack.push({ n: currentN, state: 2 });
                stack.push({ n: currentN - 2, state: 0 });
                break;
            case 2:
                // 阶段2：所有子递归都执行完了，执行doStuff
                doStuff(currentN);
                break;
        }
    }
}

执行逻辑说明（以n=3为例） #

1. 初始栈：[{n:3, state:0}]
2. 弹出{3,0}，因为state=0，压回{3,1}，再压入{2,0} → 栈变为[{3,1}, {2,0}]
3. 弹出{2,0}，压回{2,1}，压入{1,0} → 栈变为[{3,1}, {2,1}, {1,0}]
4. 弹出{1,0}，压回{1,1}，压入{0,0} → 栈变为[{3,1}, {2,1}, {1,1}, {0,0}]
5. 弹出{0,0}，因为n<=0，直接跳过 → 栈变为[{3,1}, {2,1}, {1,1}]
6. 弹出{1,1}，压回{1,2}，压入{-1,0} → 栈变为[{3,1}, {2,1}, {1,2}, {-1,0}]
7. 弹出{-1,0}，跳过 → 栈变为[{3,1}, {2,1}, {1,2}]
8. 弹出{1,2}，执行doStuff(1) → 栈变为[{3,1}, {2,1}]
9. 后续以此类推，最终会按递归的顺序执行doStuff(1)→doStuff(2)→doStuff(3)，和原始递归的执行结果完全一致。

通用性扩展 #

不管递归函数里有多少个递归调用，只要给每个栈元素添加对应的状态阶段，分步骤压栈待执行的子调用，就能准确模拟递归的执行顺序。本质上就是把JS引擎自动管理的调用栈，手动用栈结构+状态标记实现出来。

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