C語(yǔ)言之遞歸排序算法

一、什么是遞歸算法?

遞歸算法是把問(wèn)題轉(zhuǎn)化為規(guī)?？s小了的同類問(wèn)題的子問(wèn)題。然后遞歸調(diào)用函數(shù)（或過(guò)程）來(lái)表示問(wèn)題的解。

一個(gè)過(guò)程(或函數(shù))直接或間接調(diào)用自己本身,這種過(guò)程(或函數(shù))叫遞歸過(guò)程(或函數(shù)).

二、遞歸算法原理、特點(diǎn)、要求及實(shí)現(xiàn)

原理

遞歸過(guò)程一般通過(guò)函數(shù)或子過(guò)程來(lái)實(shí)現(xiàn)。遞歸方法：在函數(shù)或子過(guò)程的內(nèi)部，直接或者間接地調(diào)用自己的算法。

特點(diǎn)

遞歸算法是一種直接或者間接地調(diào)用自身算法的過(guò)程。在計(jì)算機(jī)編寫(xiě)程序中，遞歸算法對(duì)解決一大類問(wèn)題是十分有效的，它往往使算法的描述簡(jiǎn)潔而且易于理解。

遞歸算法解決問(wèn)題的特點(diǎn)：

(1) 遞歸就是在過(guò)程或函數(shù)里調(diào)用自身。

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

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

(4) 在遞歸調(diào)用的過(guò)程當(dāng)中系統(tǒng)為每一層的返回點(diǎn)、局部量等開(kāi)辟了棧來(lái)存儲(chǔ)。遞歸次數(shù)過(guò)多容易造成棧溢出等。所以一般不提倡用遞歸算法設(shè)計(jì)程序。

要求

遞歸算法所體現(xiàn)的“重復(fù)”一般有三個(gè)要求：

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

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

3)是在問(wèn)題的規(guī)模極小時(shí)必須用直接給出解答而不再進(jìn)行遞歸調(diào)用，因而每次遞歸調(diào)用都是有條件的(以規(guī)模未達(dá)到直接解答的大小為條件)，無(wú)條件遞歸調(diào)用將會(huì)成為死循環(huán)而不能正常結(jié)束。

三、C語(yǔ)言程序代碼

#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是第一個(gè)元素的下標(biāo),2是最后一個(gè)元素的下標(biāo) 
printf("總共有%d中排列",count);
return 0;
 
} 
void  perm(char *list,int q,int p)//排序函數(shù) 
{
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開(kāi)頭的,后面是bc的所有排列
// swap(list[0],list[0],tmp);
// perm(list,1,2);
// swap(list[0],list[0],tmp);
// b開(kāi)頭的,后面是ac的所有排列
// swap(list[0],list[1],tmp);//a和b交換 
// perm(list,1,2); 
// swap(list[0],list[1],tmp);
// c開(kāi)頭的,后面是ab的所有排列
// swap(list[0],list[2],tmp);//a和c交換 
// perm(list,1,2); 
// swap(list[0],list[2],tmp);
}