遞歸對於編程者來說，是比較難理解的，但當你完全清晰程序思路時，它會變得容易理解了。
遞歸思想成為解決一些編程難題所常用的，所以多多練習，多多理解它，會讓我們對之愛不釋手，作為初學者的我，每當理解如何遞歸的解決問題時，就會非常開心，這也許就是挑戰所帶來的成就感，所學即所得的滿足感吧。
下面以如下一道例題為例吧：
在數據結構（c語言版）一書中，頁碼p8，有如下一題
問題1：<全排列>對給定的n個元素的集合，輸出該集合所有可能的排列；
我們對比著看下面一道問題，可以先思考思考：
問題2：<全排列>對給定的n個元素的序列（可能含重復元素），輸出該序列所有可能的排列。（後面來解析該題。）
我們來先說說問題1吧：
即然是n個元素的集合，那麼由眾所周知的集合定義，我們可以明確得出：這n個元素是互不相同的。
那麼問題轉換為求n個不重復元素的全排列，同問題2有著顯著區別哦。
對於該問題：
首先對於全排列：
首字符是這n個元素中的其中一個，如果首字符不同，我們得到的排列也必是不同的。
其次：（核心思想）
我們可以先預定某個元素為首字符，再對剩余字符進行全排列（嘿嘿，此處是不是回歸到我們開始要求的問題了呀，只不過此處變成了對n-1的全排列了啊，這這。。。顯然明確是遞歸的結構啊）
最後：
我們循環的將首字符換成與之前不同的字符（這句話要好好理解，問題2的小核心），再對剩余進行全排列，直至首字符遍歷完n個元素。
文字太枯燥，來個例子，比如：對{a,b,c,d}進行全排列，
以a為頭，對{b,c,d}進行全排列
以b為頭，對{a,c,d}進行全排列
以c為頭，對{a,b,d}進行全排列
以d為頭，對{a,b,c}進行全排列
問題的規模，在遞歸的結構下，由規模4變成了規模3了，然後規模3又在遞歸的結構下變成了規模2.。。。。。最後遞歸到只有1個規模了，那麼此時，說明當前遞歸已到遞歸基上了，說明已進行了一次全排列。此時我們就可以輸出當前的排列了。
運行到此處，我們還要注意些程序實現的細節，不然很難實現最終的結果哦。
先上個代碼，代碼裡有相關說明，會讓你更明白些。
#include<iostream> void perm(char*,int,int);
int main()
{
using namespace std;
char* p=new char[4];
for(int i=0;i<4;i++)
cin >> *(p+i);
perm(p,0,3);
cout << num;
for(int i=0;i<4;i++)
cout << p[i] << "--";
delete[] p;
return 0;
}
//遞歸產生的全排列
void perm(char* p,int a,int b) //a表示待全排的數組下標開始，b表示下標尾
{
if(a == b) //遞歸基，說明只有一個元素了
{
for(int i=0;i<=b;i++) //此時按下標順序輸出當前數組中的元素，因為數組通過交換元素的方式實現了排列。
{
std::cout << p[i];
}
std::cout << std::endl;
}
else
{
for(int j=a;j<=b;j++) //該處的循環作用就是，讓首字符取遍所有可能字符，每次循環，都會將首字符為當前循環
//字符的所有可能排列全部輸出
{
std::swap(p[a],p[j]); //此處就是通過交換元素的方式讓當前首字符更改，不同於之前循環，也惟有這樣處理，、
//首字符才可能取遍所有可能字符
perm(p,a+1,b); //此處遞歸調用，因為首字符我們已經確定了，我們只需對剩余元素進行全排列，所以只需作a+1處理即可
std::swap(p[a],p[j]); //將數組還原到初始狀態，對於此處，開始我比較難理解，下面畫個調用圖，看看它是如何還原的
}
}
}
為了簡化時序分析，我們這裡分析的是3個元素的全排序，其調用如下圖所示：
我們可以在這裡清晰的看到調用的過程，以及相關變量的值變化。我們如果由3個元素推廣更多的元素，我們會發現其中很多自相似的調用圖譜。另外我們也注意到，在一個完整的for循環中，每個循環開始前，p數組的序列都是一樣的。
主要由於兩個swap的作用，也算是此處的小核心了。
也惟有保證每次循環前，p序列回歸原始狀態，我們才能保證下次循環開始，將下一個不同的字符放在首字符。
下面這個圖畫的略草，但還可以湊和著看了。
#include<iostream>
void perm(char*,int,int);
int main()
{
using namespace std;
bool flag=true;
while(flag)
{
cout << "input the number:";
int n;
cin >> n;
cout << "enter " << n << " character:";
char* p=new char[n];
for(int i=0;i<n;i++)
cin >> *(p+i);
perm(p,0,n-1);
cout << "continue?(y/n)";
char ch;
cin >> ch;
if(ch!='y')
{
flag=false;
}
delete[] p;
}
return 0;
}
void perm(char* p,int a,int b)
{
if(a == b)
{
for(int i=0;i<=b;i++)
{
std::cout << p[i];
}
std::cout << std::endl;
}
else
{
for(int j=a;j<=b;j++)
{
bool flag = false;
for(int i=a;i<j;i++)
{
if(p[i]==p[j])
{
flag = true;
}
}
if(flag)
{
continue;
}
std::swap(p[a],p[j]);
perm(p,a+1,b);
std::swap(p[a],p[j]);
}
}
}
運行結果如下：
#include<iostream>
void perm(char*,int,int,int&);
int main()
{
using namespace std;
bool flag=true;
while(flag)
{
int num=0;
cout << "input the number:";
int n;
cin >> n;
cout << "enter " << n << " character:";
char* p=new char[n];
for(int i=0;i<n;i++)
cin >> *(p+i);
perm(p,0,n-1,num);
cout << "the number of permutation:" << num << endl;
cout << "continue?(y/n)";
char ch;
cin >> ch;
if(ch!='y')
{
flag=false;
}
delete[] p;
}
return 0;
}
void perm(char* p,int a,int b,int& num)
{
if(a == b)
{
num++;
}
else
{
for(int j=a;j<=b;j++)
{
bool flag = false;
for(int i=a;i<j;i++)
{
if(p[i]==p[j])
{
flag = true;
}
}
if(flag)
{
continue;
}
std::swap(p[a],p[j]);
perm(p,a+1,b,num);
std::swap(p[a],p[j]);
}
}
}
運行結果如下：
