Automatically refactor a loop into a recursive method?

Question

Do you know a tool that automatically refactors a method with a single loop into a recursive method, preferably in Java?

This is for teaching purposes.

Answer 1

I don't think such a tool exists, since usually refactoring aims at increasing performance, not decreasing it (which is the case when using recursive methods instead of loops). If it is for teaching purposes, why not make the students create the tool that would do that? This way, they could learn at the same time recursion and parsing.

I don't know if the recursification can be automated, but here's what the transformation should look like. Let's take a generic for loop, in pseudo-code, for the sake of demonstration:

loopFunc() // method (could return a value or not)
{
    for (initialization ; // Sets the context
         test ;           // Test continuation wrt the context
         counting_exp     // Update the context after each iteration
        ) 
    { 
        loop_body
    }
}

The loop is composed of four parts: initialization, which initialize the context (usually variables); test, which is a boolean expression that checks wheter or not the loop is finished; counting_exp, which is a statement that is performed after each iteration; and finally, loop_body, that represents the operations that are executed at each iteration.

A recursive version of this method should be decomposed in two parts: one for initialization, and the other one to actually perform the loop:

recFunc()
{
    initialization        // Sets the context
    innerRecFunc(context) // We need to pass the context to the inner function
}

innerRecFunc(context)
{
    if not test then return // could return a value
    else
    {
        loop_body             // Can update context
        counting_exp          // Can update context
        innerRecFunc(context) // Recursive call (note tail-recursion)
    }
}

I didn't think about the problem enough to be 100% sure that this would work in all cases, but for simple loops this should be correct. Of course, this transformation can easily be adapted to other types of loops (while, do while).

Answer 2

I'm not entirely sure that this is even possible in the generic sense, as it seems to me like a variation of the halting problem.

Answer 3

If you are doing this for teaching purposes I would think you can get away with doing it for a very limited set of cases. So could you just write something that took

myMethod() {
  // startcode
  for (init,cond,incr) {
    // loopcode
  }
  //endcode
}

and transformed it to

myMethod() {
  //startcode
  init;
  recursive(value);
  //endcode
}
recursive(value) {
  if (!cond) {
    return
  } else {
    //loopcode
    incr;
    recursive(value);
}

I'm sure you can sort out the pseudocode for yourself.