将递归函数转换为for循环？ [英] Turning a recursive function into a for loop?

问题描述

每个递归函数都有一个等价的循环？ （两者都达到相同的结果）。

我有这个递归函数：

  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）; 
返回recur（word，length-1）; 
 
 
 
 
 
 $ b 
鉴于单词是一个Set []，并且其中单词[i] =一个单词长度为i的集合。
 
 
试图做的是：
用一个单词发起递归（比如说stackoverflow，没有空格） ，我试图找出这个单词是否可以被切割成子字（堆，上，流）。一个子词的最小长度是3，并且假定长度为i的子词在集合词中[b] 
 
 
我可以确认这个代码有效，但是它可能有内存问题，所以我想把它变成一个循环..如果可能的话。 > 
 
 
你需要更多的信息吗？ 
 
 
谢谢。 
 
 
 
  private static boolean recur（String word，int length）{
 if（length == 1 || length == 2）
 return false ; 
 if（length == 0）
 return true; 
 int nextLength; 
字符串nextWord; 
 if（words [length] .contains（word.substring（0，length）））{
 nextWord = word.substring（length）; 
 nextLength = word.length（） - 长度; 
} else {
 nextWord = word; 
 nextLength = length  -  1; 
} 
 return recur（nextWord，nextLength）; 
 
 
 
 $ b $ p $这是现在正确的尾递归。现在把它变成一个循环： 
 
 
  private static boolean recur（String word，int length）{
 int nextLength =长度; 
字符串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; 
 
 
 
 
 
 
注意这个代码可以是进一步优化，我只是想演示递归循环的自动方法。
Does every recursive function have an equivalent for loop? (Both achieve the same result).

I have this recursive function:
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);
}
Given that words is a Set[], and where words[i] = a set with words of length 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.

Do you need more info??

Thanks.
解决方案
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屋！