問題描述

我發現遞歸，除了像階乘這樣非常直接的遞歸，非常難以理解.以下代碼段打印字符串的所有排列.誰能幫我理解一下.正確理解遞歸的方法是什么.

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

這篇關于了解遞歸以生成排列的文章就介紹到這了，希望我們推薦的答案對大家有所幫助，也希望大家多多支持html5模板網！