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

Question

每个递归函数都有一个等效的循环吗？(两者都达到了相同的效果).

我有这个递归函数:

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",没有空格),我试图找出这个单词是否可以切成子词("堆栈","结束","流程") ..子词的最小长度是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