理解递归生成置换

Question

我发现递归，除了像阶乘这样的直截了当的递归之外，很难理解。下面的代码片段打印字符串的所有排列。有人能帮我理解吗。正确理解递归的方法是什么。

void permute(char a[], int i, int n)
{
   int j;
   if (i == n)
     cout << a << endl;
   else
   {
       for (j = i; j <= n; j++)
       {
          swap(a[i], a[j]);          
          permute(a, i+1, n);
          swap(a[i], a[j]);
       }
   }
} 

int main()
{
   char a[] = "ABCD";
   permute(a, 0, 3);
   getchar();
   return 0;
}

Answer 1

要在设计中有效地使用递归，可以通过假设已经解决了问题来解决问题。 当前问题的心理跳板是“如果我能计算出n-1个字符的排列，那么我就可以依次选择每个字符并附加其余n-1个字符的排列来计算n个字符的排列，我假装我已经知道该怎么做了”。

然后你需要一种方法来完成所谓的“触底”递归。因为每个新的子问题都比上一个小，也许你最终会得到一个你真正知道如何解决的子问题。

在这种情况下，你已经知道了一个角色的所有排列-它只是一个角色。所以你知道如何求解n=1，对于每一个数，这个数比你能求解的数多一个，你就完成了。这与所谓的数学归纳法密切相关。

Answer 2

它从所有可能剩下的字符中选择每个字符：

void permute(char a[], int i, int n)
{
    int j;
    if (i == n)                  // If we've chosen all the characters then:
       cout << a << endl;        // we're done, so output it
    else
    {
        for (j = i; j <= n; j++) // Otherwise, we've chosen characters a[0] to a[j-1]
        {                        // so let's try all possible characters for a[j]
            swap(a[i], a[j]);    // Choose which one out of a[j] to a[n] you will choose
            permute(a, i+1, n);  // Choose the remaining letters
            swap(a[i], a[j]);    // Undo the previous swap so we can choose the next possibility for a[j]
        }
    }
} 

Answer 3

保罗的建议是对的。在理解代码之前，你必须用“手”（使用你想要的任何工具——调试器、纸张、记录函数调用和变量）来浏览代码。关于代码的解释，我将向您介绍quasiverse的优秀答案。

也许，这种调用图的可视化（字符串稍微小一点）使其工作方式更加明显：

这张图是用graphviz绘制的。

// x.dot
// dot x.dot -Tpng -o x.png
digraph x {
rankdir=LR
size="16,10"

node [label="permute(\"ABC\", 0, 2)"] n0;
 node [label="permute(\"ABC\", 1, 2)"] n1;
  node [label="permute(\"ABC\", 2, 2)"] n2;
  node [label="permute(\"ACB\", 2, 2)"] n3;
 node [label="permute(\"BAC\", 1, 2)"] n4;
  node [label="permute(\"BAC\", 2, 2)"] n5;
  node [label="permute(\"BCA\", 2, 2)"] n6;
 node [label="permute(\"CBA\", 1, 2)"] n7;
  node [label="permute(\"CBA\", 2, 2)"] n8;
  node [label="permute(\"CAB\", 2, 2)"] n9;

n0 -> n1 [label="swap(0, 0)"];
n0 -> n4 [label="swap(0, 1)"];
n0 -> n7 [label="swap(0, 2)"];

n1 -> n2 [label="swap(1, 1)"];
n1 -> n3 [label="swap(1, 2)"];

n4 -> n5 [label="swap(1, 1)"];
n4 -> n6 [label="swap(1, 2)"];

n7 -> n8 [label="swap(1, 1)"];
n7 -> n9 [label="swap(1, 2)"];
}