如何将多次递归调用的递归转换为迭代？我已经知道只有一次递归调用时该怎么做

Question

这是我如何转换只有一次递归调用的递归函数（我将使用 JavaScript）

function f(n){
    if(n>0){
        f(n-1);
        doStuff(n); //this could be anything
    }
}

迭代形式

function f(n){
    let stack = [];
    while(n>0){
        stack.push(n);
        n = n-1;
    }
    while(stack.length!=0){
        doStuff(stack.pop());
    }
}

但是我不知道如何实现这样的功能

function f(n){
    if(n>0){
        f(n-1);
        f(n-2); //how to deal with this?
        doStuff(n);
    }
}

Answer 1

您可以在堆栈上放置更多信息，例如 what 与堆栈上的值做什么：执行

f

，或执行

doStuff

。

那么它就可以变成这样：

function f(n) {
    const stack = [[0, n]];
    while (stack.length) {
        const [state, n] = stack.pop();
        if (state) {
            doStuff(n);
        } else if (n > 0) {
            // Three tasks to perform -- stack in reverse order
            stack.push([1, n], [0, n-2], [0, n-1]);
        }
    }
}