我已经编写了有关如何使用 for 循环查找给定字符串的排列的代码。我遵循了教授的伪代码,但不确定如何将其转换为递归。 (没有 for、goto、while、STL 算法)。
void perms(string prefix, string rest)
{
// Followed Format of Pseudocode that Professor gave us
// If nothing remains in the rest string cout what we have for prefix
if (rest == "")
{
cout << prefix << endl;
}
else
{
for (int i = 0; i < rest.length(); i++)
{
string prefix2 = prefix + rest[i];
string rest2 = rest.substr(0, i) + rest.substr(i + 1);
perms(prefix2, rest2);
}
}
}
代码运行良好,只是需要帮助将其转换为递归。
最佳答案
要将循环提升为递归,您必须将迭代变量 i
转换为参数:
第一步:
void printPermutations(string prefix, string rest, int i = 0)
第 2 步:
void printPermutations(string prefix, string rest, int i = 0)
{
// Followed Format of Pseudocode that Professor gave us
// If nothing remains in the rest string cout what we have for prefix
if (rest == "")
{
cout << prefix << endl;
}
else if (i < rest.length())
{
// original loop body
string prefix2 = prefix + rest[i];
string rest2 = rest.substr(0, i) + rest.substr(i + 1);
// true original recursion with different prefix and tail.
printPermutations(prefix2, rest2);
// loop continuation via tail recursion: original prefix, next i.
printPermutations(prefix, rest, i + 1);
}
}
这几乎是机械改造。首先,将 i
初始化为 0
已移至参数列表中,我们通过默认设置来执行此操作(必要时,我们也可以让调用者显式传递零)。循环的 for
循环 header 已被删除,仅替换为循环保护条件,该条件被转换为 if
条件。然后循环的继续只是通过我们传递 i + 1
的尾部调用完成的,它成为 i
的下一个值。
想象一下这个仍在迭代的中间版本可能会有所帮助:
void printPermutations(string prefix, string rest)
{
int i = 0;
topOfFunction:
// Followed Format of Pseudocode that Professor gave us
// If nothing remains in the rest string cout what we have for prefix
if (rest == "")
{
cout << prefix << endl;
}
else if (i < rest.length())
{
// original loop body
string prefix2 = prefix + rest[i];
string rest2 = rest.substr(0, i) + rest.substr(i + 1);
// true original recursion with different prefix and tail.
printPermutations(prefix2, rest2);
// loop continuation via tail recursion: original prefix, next i.
i = i + 1;
goto topOfFunction;
}
}
请注意,虽然 rest == ""
检查包含在循环中,但我们知道它保持为 false,因为我们从未修改 rest
。
关于c++ - 迭代/递归,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/57316429/