将递归函数转换为for循环？

Z时代
2024-01-10
分类：问答

是否每个递归函数都有一个等效的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]中。

我可以确认此代码有效，但可能存在内存问题，因此，如果可能，我想将其转为循环。

您需要更多信息吗？

谢谢。

回答：

尾递归总是可以展开到循环中，并且您的代码 ~~非常接近~~ 尾递归，所以可以。

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