Réorganiser automatiquement une boucle en une méthode récursive?

Question

Connaissez-vous un outil qui refactorise automatiquement une méthode avec une seule boucle en une méthode récursive, de préférence en Java?

Ceci est à des fins d'enseignement.

Answer 1

Je ne pense pas qu'un tel outil existe, car le refactoring vise généralement à augmenter les performances, pas à les diminuer (ce qui est le cas lorsque l'on utilise des méthodes récursives au lieu de boucles). Si c'est à des fins d'enseignement, pourquoi ne pas faire en sorte que les élèves créent l'outil qui ferait cela? De cette façon, ils pourraient apprendre en même temps la récursivité et l'analyse syntaxique.

Je ne sais pas si la récursivité peut être automatisée, mais voici à quoi devrait ressembler la transformation. Prenons un générique pour la boucle, en pseudo-code, pour le bien de démonstration:

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

La boucle se compose de quatre parties: initialization, qui initialisent le contexte (variables en général); test, qui est une expression booléenne qui vérifie si la boucle est terminée ou non; counting_exp, qui est une instruction exécutée après chaque itération; et enfin, loop_body, qui représente les opérations qui sont exécutées à chaque itération.

Une version récursive de cette méthode doit être décomposé en deux parties: l'une pour l'initialisation, et l'autre pour effectuer réellement la boucle:

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

Je ne pensais pas le problème assez à 100 % sûr que cela fonctionnerait dans tous les cas, mais pour les boucles simples, cela devrait être correct. Bien sûr, cette transformation peut facilement être adaptée à d'autres types de boucles (while, do while).

Answer 2

Je ne suis pas entièrement sûr que cela soit même possible dans le sens générique, car il me semble être une variation de the halting problem.

Answer 3

Si vous faites cela à des fins d'enseignement, je pense que vous pouvez vous en sortir en faisant cela pour un nombre très limité de cas. Pourriez-vous écrire quelque chose qui a pris

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

et transformé à

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

Je suis sûr que vous pouvez régler le pseudo-code pour vous-même.