Автоматически реорганизовать цикл в рекурсивный метод?

Question

Знаете ли вы инструмент, который автоматически реорганизует метод с одним циклом в рекурсивный метод, желательно на Java?

Это предназначение для обучения.

Answer 1

Я не думаю, что такой инструмент существует, поскольку обычно рефакторинг нацелен на повышение производительности, а не на уменьшение его (что имеет место при использовании рекурсивных методов вместо циклов). Если это для учебных целей, почему бы не заставить учащихся создать инструмент, который бы это сделал? Таким образом, они могли бы учиться в то же время рекурсии и разбора.

Я не знаю, можно ли автоматизировать рекурсию, но вот как должно выглядеть преобразование. Давайте возьмем общий цикл, в псевдокоде, для демонстрации:

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

Цикл состоит из четырех частей: initialization, которые инициализировать контекст (обычно переменные); test, который является булевым выражением, которое проверяет, завершает ли цикл или нет; counting_exp, который является инструкцией, выполняемой после каждой итерации; и, наконец, loop_body, который представляет операции, выполняемые на каждой итерации.

Рекурсивная версия этого метода должна быть разложена на две части: одна для инициализации, а другой на самом деле выполнить цикл:

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

Я не думал об этой проблеме достаточно, чтобы быть 100 % уверен, что это будет работать во всех случаях, но для простых циклов это должно быть правильно. Конечно, это преобразование может быть легко адаптировано к другим типам петель (while, do while).

Answer 2

Я не совсем уверен, что это возможно даже в общем смысле, как мне кажется, как вариант the halting problem.

Answer 3

Если вы делаете это в целях обучения, я думаю, вы можете уйти от этого для очень ограниченного набора случаев. Так что вы могли бы просто написать что-то, что взял

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

и превратили его в

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

Я уверен, что вы можете разобраться в псевдокод для себя.