3

每个递归函数都有一个等价的 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);
}

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

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

我可以确认这段代码有效，但它可能有内存问题，所以我想把它变成一个循环......如果可能的话。

您需要更多信息吗？

谢谢。

4

5 回答 5

6

尾递归总是可以展开成一个循环，你的代码非常接近尾递归，所以是的。

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

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

于 2011-02-10T11:21:12.930 回答
5

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

针对具体问题：

将您的代码视为一个函数并忽略副作用，我认为您可以返回 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
于 2011-02-10T11:22:02.717 回答
2

简短的回答：通常你可以，在这种情况下你可以很容易，但如果你修复代码逻辑中的错误，你必须担心自己维护堆栈。

长答案：

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

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

这通过将递归调用替换为对参数的赋值并将其全部粘贴在一个循环中来实现。

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

（我想不出这个错误可以使用的实际单词，所以想象我虚构的单词是真实的单词。）

假设你的长词是 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);
}

现在，把它变成一个迭代方法更难了：有时你有两个递归调用。这意味着简单地分配给您的参数是行不通的，因为您需要参数的原始值来计算第二次调用的参数。您必须显式管理具有所有不同值的堆栈或队列，因为现在该语言不为您做这件事。

于 2011-02-10T11:19:57.327 回答
1

我回答你的第一个问题：是的，每个递归函数都有一个迭代等价物。阅读更多。

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

于 2011-02-10T11:18:32.903 回答
0

@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;
    }
}
于 2011-02-10T11:44:20.463 回答