java - 自动将循环重构为递归方法？

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，这是一个 boolean 表达式，用于检查循环是否完成； 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)。