我发现递归,除了像阶乘这样非常直接的递归,很难理解。以下代码段打印字符串的所有排列。谁能帮我理解一下。正确理解递归的方法是什么。
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 的出色答案。
也许这种调用图的可视化使用稍小的字符串使其工作原理更加明显:
图表是用 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)"];
}
关于c++ - 了解递归以生成排列,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/7537791/