How to convert a recursion with multiple recursive calls into an iteration? I already know how to do it when there is only one recursive call

Question

Here is how I would convert a recursive function that only has one recursive call (I'll use JavaScript)

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

Iterative form

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

But I don't know how to go about a function like this

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

Answer 1

You could put a bit more information on the stack, like what to do with the value on the stack: perform f, or perform doStuff.

So then it can become like this:

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

Note that this approach also works for your first example, where you only have one recursive call. The only statement that needs to change (in the above code) is the push call:

            stack.push([1, n], [0, n-1]);