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

var fact=function(n){ return n==0?1:n*fact(n-1); };

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

Now let’s look at more complicated examples:

##### fibonacci number

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

##### hanoi tower

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

##### merge sort

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

Howdy! Would you mind if I share your blog with my zynga group? There’s a lot of people that I think would really appreciate your content. Please let me know. Cheers

Go ahead.

I often visit your page and have noticed that you don’t update it often.

More frequent updates will give your page higher authority & rank in google.

I know that writing articles takes a lot of time, but you can always

help yourself with miftolo’s tools which will shorten the time

of creating an article to a couple of seconds.

Thanks for the feedback.

This design is steller! You

Hey! This is my 1st comment here so I just wanted to give a quick shout out and say I really enjoy reading your

posts. Can you recommend any other blogs/websites/forums that deal with

the same subjects? Thanks for your time!

You need to take part in a contest for one of the best sites on the web. I’m going to highly recommend this site!