c++ - 迭代/递归

Question

我已经编写了有关如何使用 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);
        }
    }
}

代码运行良好，只是需要帮助将其转换为递归。

Answer 1

要将循环提升为递归，您必须将迭代变量 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。