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