了解递归以生成排列

2021-12-16 00:00:00 递归 c++

我发现递归，除了像阶乘这样非常直接的递归，非常难以理解.以下代码段打印字符串的所有排列.谁能帮我理解一下.正确理解递归的方法是什么.

I find recursion, apart from very straight forward ones like factorial, very difficult to understand. The following snippet prints all permutations of a string. Can anyone help me understand it. What is the way to go about to understand recursion properly.

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 的优秀答案.

PaulR has the right suggestion. You have to run through the code by "hand" (using whatever tools you want - debuggers, paper, logging function calls and variables at certain points) until you understand it. For an explanation of the code I'll refer you to quasiverse's excellent answer.

也许这个调用图的可视化用稍微小一点的字符串使它的工作原理更加明显:

Perhaps this visualization of the call graph with a slightly smaller string makes it more obvious how it works:

该图是使用 graphviz 制作的.

The graph was made with 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)"];
}

相关文章