java - 将递归函数转换为 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);
}

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

我想做的是: 用一个词(比如“stackoverflow”，没有空格)启动递归，我试图找出这个词是否可以被切割成子词(“stack”，“over”，“flow”)..子词的最小长度为3，假设长度为i的子词在集合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;
        }
    }
}

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