将递归函数转换为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”，没有空格），我试图找出这个单词是否可以切成子词（“堆栈”，“结束”，“流程”） ..子词的最小长度是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; } } }
请注意，此代码可以进一步优化，我只是想演示将递归转换为循环的“自动”方法。
对于一般问题：是的，每个递归都可以在循环中转换。 您可以明确地对递归创建和使用的堆栈进行建模，并在循环中对其进行修改。
针对具体问题：
将您的代码看作一个函数并忽略副作用我认为您可以返回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
简短的回答：一般情况下，你可以很容易地，但是如果你修复代码逻辑中的错误，你必须担心自己维护堆栈。
答案很长：
首先，递归方法的迭代版本：
private static boolean recur(String word, int length) { while(true) { if(length == 1 || length == 2) return false; if(length == 0) return true; if(words[length].contains(word.substring(0, length))) { int newlen = word.length() - length; word = word.substring(length); length = newlen; } else { --length; } } }
这可以通过将参数赋值替换为递归调用，并将其全部放在循环中来实现。
但就像你的原始代码一样，这包含一个错误！
（我无法想到这个错误适用的实际词汇，所以想象一下我编造的单词是真实的单词。）
假设你的长词是ABCDEFGH，ABCD，EFGH和ABCDE都是单词，但FGH不是。 recur寻找最长的单词，所以它会匹配ABCDE，然后发现FGH不是一个单词，并告诉你ABCDEFGH不能被切成子词。
但它可以分为ABCD和EFGH！ 它错过了较短的初始匹配，因为一旦找到匹配项，您就不会考虑其他选项。 （如果你的代码是通过寻找较短的匹配开始的，那么如果ABC是一个单词并且DEFGH不是，那么它仍然无效。）
所以：
private static boolean recur(String word, int length) { if(length == 1 || length == 2) return false; if(length == 0) return true; return (words[length].contains(word.substring(0, length))) && recur(word.substring(length), word.length() - length)) || recur(word, length-1); }
现在，将其转换为迭代方法更难：有时您有两个递归调用。 这意味着简单地分配您的参数将不起作用，因为您需要参数的原始值来计算第二次调用的参数。 您必须显式管理具有所有不同值的堆栈或队列，因为现在语言不会为您执行此操作。
我回答你的第一个问题：是的，每个递归函数都有一个迭代等价物。 阅读更多 。
这也与CPS有关（不完全是因为流行的Java VM并不真正支持尾调用）。 转换尾递归函数（例如问题中的函数）应该特别容易。
@biziclop演示了如何重构代码是非递归的。 我会进一步减少代码，以便。
-
length不再作为参数传递。 - 两个循环用于简化逻辑。
- 修改本地字值以简化。
码
private static boolean recur(String word) { LOOP: for(;;) { for (int len = word.length(); len >= 3; len--) if (words[len].contains(word.substring(0, len))) { word = word.substring(len); continue LOOP; } return word.length() == 0; } }