将递归函数变成for循环？

Question

每个递归函数都有一个等效的 for 循环吗？ （两者达到相同的结果）。

我有这个递归函数：

private static boolean recur(String word, int length) {
    if(length == 1 || length == 2)
        return false;
    if(length == 0)
        return true;
    if(words[length].contains(word.substring(0, length)))
        return recur(word.substring(length), word.length() - length);
    return recur(word, length-1);
}

假设单词是一个 Set[]，并且单词 [i] = 单词长度为 i 的集合。

我想做的是： 用一个单词（比如“stackoverflow”，没有空格）启动递归，我试图找出这个单词是否可以被切成子单词（“stack”，“over”，“flow”）..子单词的最小长度是 3，并且假设长度 i 的子字在 Set Words[i] 中。

我可以确认这段代码有效，但它可能有内存问题，所以我想将其转换为循环..如果可能的话。

您需要更多信息吗？

谢谢。

Answer 1

尾递归始终可以展开为循环，并且您的代码非常接近尾递归，所以是的。

private static boolean recur(String word, int length) {
    if(length == 1 || length == 2)
        return false;
    if(length == 0)
        return true;
    int nextLength;
    String nextWord;
    if(words[length].contains(word.substring(0, length))) {
      nextWord = word.substring(length);
      nextLength = word.length() - length;
    } else {
      nextWord = word;
      nextLength = length - 1;
    }
    return recur(nextWord, nextLength);
}

现在这就是正确的尾递归。现在将其变成循环：

private static boolean recur(String word, int length) {
    int nextLength = length;
    String nextWord = word;
    while( true ) {
        if(nextLength == 1 || nextLength == 2)
            return false;
        if(nextLength == 0)
            return true;
        if(words[nextLength].contains(nextWord.substring(0, nextLength))) {
            nextWord = nextWord.substring(nextLength);
            nextLength = nextWord.length() - nextLength;
        } else {
            nextWord = nextWord;
            nextLength = nextLength - 1;
        }
    }
}

请注意，这段代码可以进一步优化，我只是想演示将递归变成循环的“自动”方法。

Answer 2

对于一般问题：是的，每个递归都可以在循环中进行转换。您可以显式地对递归创建和使用的堆栈进行建模，并在循环中对其进行修改。

对于具体问题：

将代码视为函数并忽略副作用，我认为您可以返回 false。

如果您确实需要拆分词，请尝试以下操作：

have a list with the word to split.
iterate until list after iteration is the same as before.
    iterate over list
        if the word can be split, replace it in the list with its parts
    end of loop
end of loop

Answer 3

简短的回答：一般来说你可以，在这种情况下你可以很容易地做到，但是如果你修复了代码逻辑中的错误，你就必须担心自己维护堆栈。

长答案：

首先，递归方法的迭代版本：

private static boolean recur(String word, int length) {
    while(true) {
        if(length == 1 || length == 2)
            return false;
        if(length == 0)
            return true;
        if(words[length].contains(word.substring(0, length))) {
            int newlen = word.length() - length;
            word = word.substring(length);
            length = newlen;
        }
        else {
            --length;
        }
    }
}

它的工作原理是用参数赋值替换递归调用，并将其全部放入循环中。

但就像您的原始代码一样，这包含一个错误！

（我想不出这个 bug 所使用的实际单词，所以想象一下我编造的单词是真实的单词。）

假设您的长单词是 ABCDEFGH，并且 ABCD、EFGH 和 ABCDE 都是单词，但 FGH 不是。 recur 首先查找最长的单词，所以会匹配ABCDE，然后发现FGH不是单词，并告诉你ABCDEFGH不能切成子词。

但它可以分为ABCD和EFGH！它会错过较短的初始匹配，因为一旦找到匹配，您就不会考虑其他选项。 （如果你的代码从寻找较短的匹配开始，如果 ABC 是一个单词而 DEFGH 不是一个单词，它仍然无法工作。）

所以：

private static boolean recur(String word, int length) {
    if(length == 1 || length == 2)
        return false;
    if(length == 0)
        return true;
    return (words[length].contains(word.substring(0, length)))
            && recur(word.substring(length), word.length() - length))
           || recur(word, length-1);
}

现在，将其转换为迭代方法更困难：有时你有 两次递归调用。这意味着简单地分配给参数是行不通的，因为您需要参数的原始值来计算第二次调用的参数。您必须显式管理具有所有不同值的堆栈或队列，因为现在该语言无法为您执行此操作。

Answer 4

我回答你的第一个问题：是的，每个递归函数都有一个迭代函数。 了解更多。

这也与 CPS 有关（不完全是因为尾部调用不受真正支持由流行的 Java VM 提供）。转换尾递归函数（例如问题中的函数）应该特别容易。

Answer 5

@biziclop 演示了如何将代码重构为非递归的。我会进一步减少代码，以便。

• length 不再作为参数传递。
• 使用两个循环来简化逻辑。
• 修改局部字值以简化。

代码

private static boolean recur(String word) {
    LOOP: for(;;) {
        for (int len = word.length(); len >= 3; len--)
            if (words[len].contains(word.substring(0, len))) {
                word = word.substring(len);
                continue LOOP;
            }
        return word.length() == 0;
    }
}