[解決済み] 順列を生成するための再帰性を理解する

質問

再帰は、階乗のような非常にわかりやすいものを除けば、非常に理解しにくいものだと思います。次のスニペットは、文字列のすべての順列を表示する。どなたか理解する手助けをしていただけませんか？再帰を正しく理解するためにはどうしたらよいのでしょうか。

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;
}

解決方法は？

PaulRが正しい提案をしています。あなたが理解できるまで、手作業で（デバッガ、紙、関数呼び出しや変数のロギングなど、好きなツールを使って）コードを実行する必要があります。コードの説明については、quasiverseの素晴らしい回答を参照してください。

コールグラフを少し小さくした文字列で可視化すると、その仕組みがよりわかりやすくなるかもしれませんね。

このグラフは グラフビズ .

// 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)"];
}