Algorithms – How to Convert Loop to Recursion or Vice Versa

algorithmsloopsrecursion

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)
{
   if(i==1) history.Add(i.ToString()+"'s result is:1.");
   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).

Best Answer

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){
    header
    while(condition){
        loop_body
    }
    return tail
}

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

foo_recursive(params){
    header
    return foo_recursion(params, header_vars)
}

foo_recursion(params, header_vars){
    if(!condition){
        return tail
    }

    loop_body
    return foo_recursion(params, modified_header_vars)
}

Et voilà; a tail recursive version of any loop. breaks and continues 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;
        }
    }
}
Related Topic