Automatisch eine Schleife in eine rekursive Methode umgestalten?

Question

Kennen Sie ein Werkzeug, das eine Methode mit einer einzelnen Schleife automatisch in eine rekursive Methode umgestaltet, vorzugsweise in Java?

Dies ist für Lehrzwecke.

Answer 1

Ich glaube nicht, dass ein solches Werkzeug existiert, da das Refactoring normalerweise darauf abzielt, die Leistung zu erhöhen, nicht zu verringern (was bei rekursiven Methoden anstelle von Schleifen der Fall ist). Wenn es zu Lehrzwecken ist, warum sollte man die Schüler nicht dazu bringen, das Werkzeug zu entwickeln, das das tun würde? Auf diese Weise konnten sie gleichzeitig Rekursion und Parsing lernen.

Ich weiß nicht, ob die Rekursion automatisiert werden kann, aber hier ist, wie die Transformation aussehen soll. Lassen Sie sich für Schleife eines generischen nehmen, in Pseudo-Code, zum Zweck der 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 
    } 
} 

Die Schleife aus vier Teilen zusammen: initialization, die den Kontext (in der Regel Variablen) zu initialisieren; test, ein boolescher Ausdruck, der prüft, ob die Schleife beendet ist oder nicht; counting_exp, was eine Anweisung ist, die nach jeder Iteration ausgeführt wird; und schließlich loop_body, das die Operationen darstellt, die bei jeder Iteration ausgeführt werden. eine für die Initialisierung und der andere die Schleife tatsächlich auszuführen:

Eine rekursive Version dieses Verfahrens sollte in zwei Teile zerlegt werden

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) 
    } 
} 

ich nicht über das Problem dachte genug 100 zu sein % sicher, dass dies in allen Fällen funktionieren würde, aber für einfache Schleifen sollte dies korrekt sein. Natürlich kann diese Transformation leicht an andere Arten von Schleifen angepasst werden (während, während).

Answer 2

Ich bin mir nicht ganz sicher, ob das überhaupt im generischen Sinn möglich ist, da es mir wie eine Variante von the halting problem vorkommt.

Answer 3

Wenn Sie dies für Lehrzwecke tun, würde ich denken, dass Sie damit für eine sehr begrenzte Anzahl von Fällen durchkommen können. So konnte man nur etwas schreiben, das

nahm

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

und verwandelt es zu

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

Ich bin sicher, dass Sie die Pseudo-Code für sich selbst in Ordnung bringen kann.