C語言之遞歸排序算法

一、什么是遞歸算法?

遞歸算法是把問題轉化為規模縮小了的同類問題的子問題。然后遞歸調用函數（或過程）來表示問題的解。

一個過程(或函數)直接或間接調用自己本身,這種過程(或函數)叫遞歸過程(或函數).

二、遞歸算法原理、特點、要求及實現

原理

遞歸過程一般通過函數或子過程來實現。遞歸方法：在函數或子過程的內部，直接或者間接地調用自己的算法。

特點

遞歸算法是一種直接或者間接地調用自身算法的過程。在計算機編寫程序中，遞歸算法對解決一大類問題是十分有效的，它往往使算法的描述簡潔而且易于理解。

遞歸算法解決問題的特點：

(1) 遞歸就是在過程或函數里調用自身。

(2) 在使用遞歸策略時，必須有一個明確的遞歸結束條件，稱為遞歸出口。

(3) 遞歸算法解題通常顯得很簡潔，但遞歸算法解題的運行效率較低。所以一般不提倡用遞歸算法設計程序。

(4) 在遞歸調用的過程當中系統為每一層的返回點、局部量等開辟了棧來存儲。遞歸次數過多容易造成棧溢出等。所以一般不提倡用遞歸算法設計程序。

要求

遞歸算法所體現的“重復”一般有三個要求：

1)是每次調用在規模上都有所縮小(通常是減半)；

2)是相鄰兩次重復之間有緊密的聯系，前一次要為后一次做準備(通常前一次的輸出就作為后一次的輸入)；

3)是在問題的規模極小時必須用直接給出解答而不再進行遞歸調用，因而每次遞歸調用都是有條件的(以規模未達到直接解答的大小為條件)，無條件遞歸調用將會成為死循環而不能正常結束。

三、C語言程序代碼

#include<stdio.h>
#define swap(x,y,t)((t)=(x),(x)=(y),(y)=(t)) 
void  perm(char *list,int q,int p);
int count;
int main(void)
{
char list[]="abcd";
perm(list,0,3);//0是第一個元素的下標,2是最后一個元素的下標 
printf("總共有%d中排列",count);
return 0;
 
} 
void  perm(char *list,int q,int p)//排序函數 
{
char tmp;
int i;
if(q==p)
{
printf("%s\n",list);
count++;
}
else
{

for(i=q;i<=p;i++) //第一次q=0,p=2,第二次q=1,第三次q=2 
{
swap(list[i],list[q],tmp);
perm(list,q+1,p);
swap(list[i],list[q],tmp);
}
}
// a開頭的,后面是bc的所有排列
// swap(list[0],list[0],tmp);
// perm(list,1,2);
// swap(list[0],list[0],tmp);
// b開頭的,后面是ac的所有排列
// swap(list[0],list[1],tmp);//a和b交換 
// perm(list,1,2); 
// swap(list[0],list[1],tmp);
// c開頭的,后面是ab的所有排列
// swap(list[0],list[2],tmp);//a和c交換 
// perm(list,1,2); 
// swap(list[0],list[2],tmp);
}