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