了解递归以生成置换

问题描述

我发现递归，除了非常直接的例如factorial，很难理解。以下代码段打印字符串的所有排列。任何人都可以帮助我理解它。正确理解递归的方式是什么。

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有正确的建议。你必须通过手（使用任何你想要的工具 - 调试器，纸，日志功能调用和变量在某些点）运行代码，直到你明白它。

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:

图表是使用制作的。

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

这篇关于了解递归以生成置换的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！