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.
-
Odd. Normally you want to go the other way, recursive into iterative.dwc– dwc2009-02-26 16:26:59 +00:00Commented Feb 26, 2009 at 16:26
-
Interesting question, do you have an algorithm description to solve this problem ?pgras– pgras2009-02-26 16:43:59 +00:00Commented Feb 26, 2009 at 16:43
Add a comment
|
3 Answers
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).
1 Comment
Tom Hawtin - tackline
But every refactoring has an equal and opposite refactoring.
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.
4 Comments
Michael Myers
But every iterative algorithm can be converted into a recursive algorithm and vice versa. Or are you talking about the "automatic" part of the question?
David Thornley
It isn't possible to determine in general if two programs are the same, but it is possible to have a set of transforms that will maintain equivalence. Changing an algorithm from iterative to recursive should work, if we disregard possible stack overflow.
Tom Hawtin - tackline
It's probably not desirable in the general sense (think side-effects), but you only really need to support a useful subset.
Henrik Paul
mmyers: yes, that's what I'm referring to. The halting problem isn't a problem either, for humans, because you can pretty easily figure out whether a particular program halts or not, by a little hands-on analysis and oogling.
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.
