我發現遞歸，除了像階乘這樣非常簡單的遞歸之外，很難理解。以下片段打印出字符串的所有排列。任何人都可以幫助我理解它。什麼是正確理解遞歸的方法。瞭解遞歸生成排列
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)"];
}
將調用堆棧可視化爲樹會很有幫助。還值得注意的是，當你進行遞歸調用時，你前進了樹的一個單獨的分支，並且在'for'或'while'循環的每一次迭代中增加了一個分支。關於這個問題的一個令人困惑的事情是在遞歸調用置換之後的第二個交換。這可以解釋爲'unswap'，並且是必需的，因爲char數組是通過引用傳遞的，而不是按值傳遞的，並且每次交換數組中的元素時，更改都可以在下游看到。 – broadbear
它選擇從所有可能的字符每個字符左：
void permute(char a[], int i, int n)
{
int j;
if (i == n) // If we've chosen all the characters then:
cout << a << endl; // we're done, so output it
else
{
for (j = i; j <= n; j++) // Otherwise, we've chosen characters a[0] to a[j-1]
{ // so let's try all possible characters for a[j]
swap(a[i], a[j]); // Choose which one out of a[j] to a[n] you will choose
permute(a, i+1, n); // Choose the remaining letters
swap(a[i], a[j]); // Undo the previous swap so we can choose the next possibility for a[j]
}
}
}
優秀答案 – nikhil
@quasiverse您在代碼中的評論對我非常有幫助，謝謝:) –
要設計有效地使用遞歸，你假定你已經解決了它解決問題。 目前問題的心理跳板是「如果我可以計算n-1個字符的排列，那麼我可以通過依次選擇每個字符並附加其餘n-1個字符的排列來計算n個字符的排列，這我假裝我已經知道如何去做「。
然後你需要一種方法來做所謂的「觸底」遞歸。由於每個新的子問題都比最後一個小，所以你最終可能會遇到一個你真正知道如何解決的子問題。
在這種情況下，您已經知道一個字符的所有排列 - 它只是字符。所以你知道如何解決它n = 1和每一個數字比你可以解決的數字多一個，而你就完成了。這與數學歸納法非常接近。
雖然這是一個老問題，並且已經回答了添加我的意見以幫助新訪客的想法。還計劃解釋運行時間而不關注遞歸調整。
我已經用C＃編寫了這個示例，但大多數程序員都很容易理解。
static int noOfFunctionCalls = 0;
static int noOfCharDisplayCalls = 0;
static int noOfBaseCaseCalls = 0;
static int noOfRecursiveCaseCalls = 0;
static int noOfSwapCalls = 0;
static int noOfForLoopCalls = 0;
static string Permute(char[] elementsList, int currentIndex)
{
++noOfFunctionCalls;
if (currentIndex == elementsList.Length)
{
++noOfBaseCaseCalls;
foreach (char element in elementsList)
{
++noOfCharDisplayCalls;
strBldr.Append(" " + element);
}
strBldr.AppendLine("");
}
else
{
++noOfRecursiveCaseCalls;
for (int lpIndex = currentIndex; lpIndex < elementsList.Length; lpIndex++)
{
++noOfForLoopCalls;
if (lpIndex != currentIndex)
{
++noOfSwapCalls;
Swap(ref elementsList[currentIndex], ref elementsList[lpIndex]);
}
Permute(elementsList, (currentIndex + 1));
if (lpIndex != currentIndex)
{
Swap(ref elementsList[currentIndex], ref elementsList[lpIndex]);
}
}
}
return strBldr.ToString();
}
static void Swap(ref char Char1, ref char Char2)
{
char tempElement = Char1;
Char1 = Char2;
Char2 = tempElement;
}
public static void StringPermutationsTest()
{
strBldr = new StringBuilder();
Debug.Flush();
noOfFunctionCalls = 0;
noOfCharDisplayCalls = 0;
noOfBaseCaseCalls = 0;
noOfRecursiveCaseCalls = 0;
noOfSwapCalls = 0;
noOfForLoopCalls = 0;
//string resultString = Permute("A".ToCharArray(), 0);
//string resultString = Permute("AB".ToCharArray(), 0);
string resultString = Permute("ABC".ToCharArray(), 0);
//string resultString = Permute("ABCD".ToCharArray(), 0);
//string resultString = Permute("ABCDE".ToCharArray(), 0);
resultString += "\nNo of Function Calls : " + noOfFunctionCalls;
resultString += "\nNo of Base Case Calls : " + noOfBaseCaseCalls;
resultString += "\nNo of General Case Calls : " + noOfRecursiveCaseCalls;
resultString += "\nNo of For Loop Calls : " + noOfForLoopCalls;
resultString += "\nNo of Char Display Calls : " + noOfCharDisplayCalls;
resultString += "\nNo of Swap Calls : " + noOfSwapCalls;
Debug.WriteLine(resultString);
MessageBox.Show(resultString);
}
步驟： 對於例如當我們將輸入作爲「ABC」傳遞時。
從主叫首次因此，從第2點到第4.2點，每個循環的總呼叫數爲5，總數爲15個呼叫+主要呼入呼叫= 16。 每次循環次數爲3時，如果條件得到執行。
從圖中我們可以看到循環計數變成總共3次6次，即3的階乘值即輸入「ABC」長度。
如果語句for循環重複「n」次來顯示示例「ABC」中的字符，即3. 總共6次（階乘次數）我們輸入if是否顯示排列。 所以總運行時間= n X n !.
我已經給出了一些靜態CallCnt變量和表來詳細瞭解每一行的執行情況。
專家，隨時編輯我的答案或評論，如果我的任何細節不清楚或不正確，我很高興糾正它們。
此代碼和參考可以幫助你瞭解它。
// C program to print all permutations with duplicates allowed
#include <stdio.h>
#include <string.h>
/* Function to swap values at two pointers */
void swap(char *x, char *y)
{
char temp;
temp = *x;
*x = *y;
*y = temp;
}
/* Function to print permutations of string
This function takes three parameters:
1. String
2. Starting index of the string
3. Ending index of the string. */
void permute(char *a, int l, int r)
{
int i;
if (l == r)
printf("%s\n", a);
else
{
for (i = l; i <= r; i++)
{
swap((a+l), (a+i));
permute(a, l+1, r);
swap((a+l), (a+i)); //backtrack
}
}
}
/* Driver program to test above functions */
int main()
{
char str[] = "ABC";
int n = strlen(str);
permute(str, 0, n-1);
return 0;
}
嘗試勾畫出來在紙上，或者你也可以嘗試通過代碼單步在調試器。 –
添加一個新的：[編寫一個C程序來打印給定字符串的所有排列]（http://www.geeksforgeeks.org/write-ac-program-to-print-all-permutations-of-a- given-string /） –
首先，遞歸只是有時會導致優雅直觀的解決方案。有時候解決方案是優雅的，但並不直觀，因爲我相信它在這裏。有時它既不優雅，也不直觀。會不會有不雅而直觀的東西？我不知道。在這種情況下，您首先需要從概念上理解如何通過交換數組中的各種元素對來創建所有置換。然後，您需要了解如何應用遞歸算法來實現此概念。它可以幫助在每一步在紙上繪製遞歸樹。 – broadbear