Recursion -> Loop

Sometimes, we need to convert recursive functions into loop for efficiency consideration, or stack size constrain. Converting tail recursion into iteration is trivial. The method we discuss in this post is a general method to convert any recursive functions into iterative ones.

The idea is to simulate stack behavior: we store frame record as a structure into a simulated stack when calling a function, and restore the top record in stack when function returns.

The record should contain 2 part of data:

  • local variable, including parameter
  • next instruction to execute(used when restoring the record)

We also need a global variable to store return value (the same as eax register).

“Next instruction to execute” can be stored using label, and we can “goto” corresponding instruction after restoring record. However, “goto” statement is not supported in some languages, and also not recommended. Thus, we use integer number to represent label id, and use switch statement to jump to different part of code.

Following example shows recursive and iterative version of factorization function. Iterative version is significantly longer in code length, and slightly slower in practice. However, iterative version can work on large input where recursive version may get stack overflow.

We select javascript to demonstrate because:

  • Dynamic type saves declaration code
  • Closure can simulate behavior of frame record perfectly (stack elements are actually functions)
  • Powerful literal value representation

[sourcecode language=”javascript”]
var fact=function(n){
return n==0?1:n*fact(n-1);
};
[/sourcecode]
[sourcecode language=”javascript”]
var Fact=function(n){
var _ret;
var stk=[];
var construct=function(n){
var l=0;
return function(){
switch(l){
case 0:
l=1;
if(n==0){
_ret=1;
stk.pop();
return;
}
stk.push(construct(n-1));
return;
case 1:
_ret*=n;
stk.pop();
return;
}
};
};
stk.push(construct(n));
while(stk){
if(stk.length==0)return _ret;
stk[stk.length-1]();
}
};
[/sourcecode]

Now let’s look at more complicated examples:

fibonacci number
[sourcecode language=”javascript”]
var Fib=function(n){
var _ret;
var stk=[];
var construct=function(n){
var l=0,a,b;
return function(){
switch(l){
case 0:
l=1;
if(n<=1){
_ret=n;
stk.pop();
return;
}
stk.push(construct(n-1));
return;
case 1:
l=2;
a=_ret;
stk.push(construct(n-2));
return;
case 2:
b=_ret;
_ret=a+b;
stk.pop();
return;
}
};
};
stk.push(construct(n));
while(true){
if(stk.length==0)return _ret;
stk[stk.length-1]();
}
}
[/sourcecode]

hanoi tower
[sourcecode language=”javascript”]
var Hanoi=function(a,b,c,n){
var stk=[];
var construct=function(a,b,c,n){
var l=0;
return function(){
switch(l){
case 0:
l=1;
if(n>0){
stk.push(construct(a,c,b,n-1));
return;
}
stk.pop();
return;
case 1:
l=2;
document.write(a+"->"+c+"<br>");
stk.push(construct(b,a,c,n-1));
return;
case 2:
stk.pop();
return;
}
};
};
stk.push(construct(a,b,c,n));
while(stk){
if(stk.length==0)return;
stk[stk.length-1]();
}
};
[/sourcecode]

merge sort

[sourcecode language=”javascript”]
var MergeSort=function(a,i,j){
if(!i)i=0;
if(!j)j=a.length;
var stk=[];
var construct=function(a,i,j){
var l=0;
var mid,t=[],x,y;
return function(){
switch(l){
case 0:
l++;
if(j-i<=1){
stk.pop();
return;
}
mid=floor((i+j)/2);
stk.push(construct(a,i,mid));
return;
case 1:
l++;
stk.push(construct(a,mid,j));
return;
case 2:
x=i, y=mid;
while(x<mid && y<j){
if(a[x]<a[y]){
t.push(a[x]);
x++;
}else{
t.push(a[y]);
y++;
}
}
while(x<mid)t.push(a[x++]);
while(y<j)t.push(a[y++]);
for(var k=i;k<j;k++)
a[k]=t[k-i];
stk.pop();
return;
}
};
};
stk.push(construct(a,i,j));
while(stk){
if(stk.length==0)return;
stk[stk.length-1]();
}
};
[/sourcecode]

Leave a Reply

Your email address will not be published. Required fields are marked *