# General way to convert a loop (while/for) to recursion or from a recursion to a loop?

This problem is mainly focusing on the algorithm, maybe something abstract and more academic.

The example is offering a thought, I wanna a generic way, so example is only used as to make us more clearly about your thoughts.

Generally speaking, a loop can be converted to a recursive.

e.g:

``````for(int i=1;i<=100;++i){sum+=i;}
``````

And its related recursive is:

``````int GetTotal(int number)
{
if (number==1) return 1;   //The end number
return number+GetTotal(number-1); //The inner recursive
}
``````

And finally to simplify this, a tail-recursive is needed:

``````int GetTotal (int number, int sum)
{
if(number==1) return sum;
return GetTotal(number-1,sum+number);
}
``````

However, most cases aren't so easy to answer and analyze. What I wanna know is:

1) Can we get a "general common way" to convert a loop (for/while……) to a recursive? And what kinds of things should we pay attention to while doing conversion? It would be better to write detailed info with some samples and your persudo theories as well as the conversion process.

2) "Recursive" has two forms: Linely recursive and Tail-Recursive. So which is better to convert? What "rule" should we master?

3) Sometimes we need to keep the "history" of recursive, this is easily be done in a loop statement:

e.g:

``````List<string> history = new List<string>();
int sum=0;
for (int i=1;i<=100;++i)
{
else
{
StringBuilder sub = new StringBuilder();

for(int j=1;j<=i;++j)
{
if(j==i) sbu.Append(j.ToString());
else
{
sub.Append(j.ToString()+"+");
}
}
sum +=i;
sbu.Append("'s result is:"+sum+Environment.NewLine);
}
}
``````

The result below is:

1's result is 1.

1+2's result is 3.

1+2+3's result is 6 …………

However I think it's hard to keep the history in a recursive, because a recursive-based algorithm focuses on to getting the last result and do a call-back return. So all of these are done through the stack maintained by the programming language assigning memory in the form of stack automatically. And how we can "manually" take each of the "stack values" out and return multiple values through a recursive algorithm?

And what about "from a recursive algorithm to a loop"? Can they be converted to each other (I think it should be done theoretically, but I want more accurate things to prove my thoughts).

• what does "persudo" mean? – gnat Jul 24 '16 at 10:06
• Maybe he meant pseudo?? As in unofficial/not necessarily scientific... – user4038800 May 20 '20 at 18:22

Actually you should break the function down first:

A loop has a few parts:

1. the header, and processing before the loop. May declare some new variables

2. the condition, when to stop the loop.

3. the actual loop body. It changes some of the header's variables and/or the parameters passed in.

4. the tail; what happens after the loop and return result.

Or to write it out:

``````foo_iterative(params){
while(condition){
loop_body
}
return tail
}
``````

Using these blocks to make a recursive call is pretty straightforward:

``````foo_recursive(params){
}

if(!condition){
return tail
}

loop_body
}
``````

Et voilà; a tail recursive version of any loop. `break`s and `continue`s in the loop body will still have to be replaced with `return tail` and return `foo_recursion(params, modified_header_vars)` as needed but that is simple enough.

Going the other way is more complicated; in part because there can be multiple recursive calls. This means that each time we pop a stack frame there can be multiple places where we need to continue. Also there may be variables that we need to save across the recursive call and the original parameters of the call.

We can use a switch to work around that:

``````bar_recurse(params){
if(baseCase){
finalize
return
}
body1
bar_recurse(mod_params)
body2
bar_recurse(mod_params)
body3
}

bar_iterative(params){
stack.push({init, params})

while(!stack.empty){
stackFrame = stack.pop()

switch(stackFrame.resumPoint){
case init:
if(baseCase){
finalize
break;
}
body1
stack.push({resum1, params, variables})
stack.push({init, modified_params})
break;
case resum1:
body2
stack.push({resum2, params, variables})
stack.push({init, modified_params})
break;
case resum2:
body3
break;
}
}
}
``````

Following up on @ratchet freak's answer, I created this example of how the Fibonacci function can be rewritten to a while loop in Java. Note that There's a much simpler (and efficient) way to rewrite the Fibonacci with a while loop though.

``````class CallContext { //this class is similar to the stack frame

Object[] args;

int resumePoint = 0;

public CallContext(Object[] args) {
this.args = args;
}

}

static int fibonacci(int fibNumber) {
Object lastReturn = null; //value of last object returned (when stack frame was dropped)
while (!callStack.isEmpty()) {
CallContext callContext = callStack.peekLast();
Object[] args = callContext.args;
//actual logic starts here
int arg = (int) args[0];
if (arg == 0 || arg == 1) {
lastReturn = arg;
callStack.removeLast();
} else {
switch (callContext.resumePoint) {
case 0: //calculate fib(n-1)
callContext.resumePoint++;
break;
case 1: //calculate fib(n-2)
callContext.resumePoint++;
break;
case 2: // fib(n-1) + fib(n-2)
• we're emulating how the call stack works with a `Deque`. – Yamcha May 22 '20 at 0:07