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

Question

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

Это для учебных целей.

Answer 1

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

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

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

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

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

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