将递归函数变成 for 循环? [英] Turning a recursive function into a for loop?

问题描述

是否每个递归函数都有等价的 for 循环?(两者都达到相同的结果).

Does every recursive function have an equivalent for loop? (Both achieve the same result).

我有这个递归函数:

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 的词的集合.

Given that words is a Set[], and where words[i] = a set with words of length i.

我想做的是:用一个词(比如stackoverflow"，没有空格)启动递归，我试图找出这个词是否可以被切成子词(stack"、over"、flow")……一个子词的最小长度是 3，并且给定长度 i 的子词在 Set words[i] 中.

What am trying to do is: initiate the recursion with a word (say, "stackoverflow", no spaces), I am trying to find if this word can be cut into subwords ("stack", "over", "flow") .. minimum length of a subword is 3, and given that the subword of lenght i is in the Set words[i].

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

I can confirm this code works, but it may have a memory problem, so I want to turn it to a loop.. if possible.

你需要更多信息吗??

谢谢.

推荐答案

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

Tail recursion can always be unrolled into a loop and your code is pretty close to tail recursion, so yes.

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

这是正确的尾递归.现在把它变成一个循环:

This is now proper tail recursion. Now to turn it into a loop:

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

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

Note that this code can be further optimised, I just wanted to demonstrate the "automatic" method of turning recursion into a loop.

这篇关于将递归函数变成 for 循环?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！