遞歸算法：基本含義，一個(gè)函數(shù)或者數(shù)學(xué)結(jié)構(gòu)，如果在其定義或說(shuō)明內(nèi)部直接或間接得出現(xiàn)對(duì)其本身的引用，或者是為了描述問(wèn)題的某一個(gè)狀態(tài)，必須要用它的上一個(gè)狀態(tài)，而描述上一個(gè)狀態(tài)，又必須用到它的上一個(gè)狀態(tài)，這種定義，稱為遞歸或遞歸定義。在程序設(shè)計(jì)上，當(dāng)函數(shù)直接調(diào)用本身或者間接調(diào)用本身，稱為遞歸調(diào)用。
遞歸的最簡(jiǎn)單應(yīng)用：通過(guò)各項(xiàng)關(guān)系及初值求數(shù)列的某一項(xiàng)。（1）
比如階乘數(shù)列
1、2、6、24、120、720……
如果用上面的方式來(lái)描述它，應(yīng)該是：
，程序?qū)崿F(xiàn)
int fun(int x)
{
if(x == 1)
return 1;
return n*fun(n-1);
}
(2)找出組合數(shù)
找出從自然數(shù)1、2、……、n中任取r個(gè)數(shù)的所有組合。例如n=5，r=3的所有組合為：
（1）5、4、3 （2）5、4、2 （3）5、4、1
（4）5、3、2 （5）5、3、1 （6）5、2、1
（7）4、3、2 （8）4、3、1 （9）4、2、1
（10）3、2、1
如何實(shí)現(xiàn)呢？
首先分析10個(gè)組合，我們可以采用遞歸來(lái)實(shí)現(xiàn)，假設(shè)函數(shù)為combo(int m,int n);為找到自然數(shù)1-m中任取K個(gè)數(shù)組合，當(dāng)?shù)谝粋€(gè)數(shù)選定后，后面的k-1個(gè)數(shù)是從m-1各數(shù)中選擇得到。我們發(fā)現(xiàn)這將是將m選k個(gè)數(shù)轉(zhuǎn)換為m-1個(gè)數(shù)中選k-1個(gè)數(shù)的組合數(shù)。為了解決此問(wèn)題，我們可以定義個(gè)數(shù)組A，數(shù)組的第一個(gè)元素為k，約定函數(shù)將確定的k個(gè)數(shù)字的組合第一個(gè)數(shù)放在A[k]中，當(dāng)一個(gè)組合求出后，才將數(shù)組A的一個(gè)組合輸出，第一個(gè)數(shù)可以是m-k，函數(shù)將確定組合的第一個(gè)數(shù)放入數(shù)組后，有兩種可能的選擇，因還未到頂組合的其余元素，繼續(xù)遞歸確定，或因一確定了組合的全部元素，輸出這個(gè)組合，
具體代碼：
//遞歸求解組合數(shù)
#define MAX 100
int a[MAX];
void combo(int m,int k)
{
int i,j;
for (i = m;i>=k;i--)
{
a[k] = i;
if (k>1)
{
comb(m-1,k-1);
}
else
{
for (j = a[0];j>0;j--)
{
printf("%4d",a[j]);
}
printf("\n");
}
}
}
更多的練習(xí)，
前幾天在博客園看到有人面試時(shí)，遇到遞歸算法題，一時(shí)手癢就解了一個(gè)。順便網(wǎng)上又找來(lái)幾個(gè)，也實(shí)現(xiàn)了。給大家分享一下，開(kāi)闊一下思路，沒(méi)準(zhǔn)你明天面試就能用上。
1、編寫一個(gè)方法用于驗(yàn)證指定的字符串是否為反轉(zhuǎn)字符，返回true和false。請(qǐng)用遞歸算法實(shí)現(xiàn)。（反轉(zhuǎn)字符串樣式為"abcdedcba"）
2、一列數(shù)的規(guī)則如下: 1、1、2、3、5、8、13、21、34...... 求第30個(gè)是多少
3、一列數(shù)的規(guī)則如下: 1、12、123、1234、12345、123456......,求第n個(gè)數(shù)的遞歸算法（n<=9）。
4、將一整數(shù)逆序，如987654321變?yōu)?23456789。
5、一個(gè)射擊運(yùn)動(dòng)員打靶,靶一共有10環(huán),連開(kāi)10槍打中90環(huán)的可能行有多少種?
posted on 2011-10-22 21:22
mengkai 閱讀(636)
評(píng)論(0) 編輯 收藏 引用 所屬分類:
algorithm