algorithmfunctionrecursioniteration

# 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

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

Solution

• 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]);
``````