當(dāng)一個(gè)問(wèn)題規(guī)模比較大且不易求解的時(shí)候，就可以考慮將問(wèn)題分成幾個(gè)小的模塊桥氏，逐一求解温峭。
分治思想和遞歸算是有親兄弟的關(guān)系，因?yàn)椴捎梅种嗡枷胩幚韱?wèn)題字支，其各個(gè)小模塊通常具有與大問(wèn)題相同的結(jié)構(gòu)凤藏，這種特性也使遞歸技術(shù)有了用武之地奸忽。
折半查找算法的遞歸實(shí)現(xiàn)(二分查找)
折半查找法是一種查找方法，該方法通過(guò)不斷縮小一半查找的范圍揖庄，直到達(dá)到目的栗菜，所以效率比較高。
二分查找遞歸實(shí)現(xiàn)代碼：
/**
* 遞歸實(shí)現(xiàn)二分查找
*/
int bin_search(int key[], int low, int high, int x){
int mid;
if (low > high)
return -1;
else{
mid = (low + high)/2;
if (key[mid] == x) return mid;
if (x > key[mid]) {
low = mid + 1;
return bin_search(key, low, high, x); // 在序列的后半部分查找
}else{
high = mid - 1;
return bin_search(key, low, high, x); //在序列的前半部分查找
}
}
}
測(cè)試：
int main(int argc, const char * argv[]) {
int str[11] = {1,1,2,3,5,8,13,21,34,55,89};
int n, addr;
printf("請(qǐng)輸入待查找的關(guān)鍵字：");
scanf("%d", &n);
addr = bin_search(str, 0, 10, n);
if (addr != -1) {
printf("查找成功蹄梢！\n關(guān)鍵字%d所在位置是：%d\n", n, addr);
}else{
printf("查找失敻沓铩！\n");
}
return 0;
}
漢諾塔問(wèn)題
漢諾塔問(wèn)題起源
漢諾塔（又稱河內(nèi)塔）問(wèn)題是源于印度一個(gè)古老傳說(shuō)的益智玩具禁炒。大梵天創(chuàng)造世界的時(shí)候做了三根金剛石柱子而咆，在一根柱子上從下往上按照大小順序摞著64片黃金圓盤(pán)。大梵天命令婆羅門(mén)把圓盤(pán)從下面開(kāi)始按大小順序重新擺放在另一根柱子上幕袱。并且規(guī)定暴备，在小圓盤(pán)上不能放大圓盤(pán)，在三根柱子之間一次只能移動(dòng)一個(gè)圓盤(pán)们豌。
漢諾塔問(wèn)題抽象成數(shù)學(xué)問(wèn)題
假設(shè)三個(gè)分別命名為X涯捻、Y、Z的塔座望迎，在塔座X上插有n個(gè)直徑大小各不相同障癌、依小到大編號(hào)為1,2,3...的圓盤(pán)，現(xiàn)在要求將X軸上的n個(gè)圓盤(pán)移動(dòng)至Z上辩尊，并按照同樣順序疊排陪拘，圓盤(pán)移動(dòng)時(shí)必須循序一下規(guī)則：
- 每次只能移動(dòng)一個(gè)圓盤(pán)常摧；
- 圓盤(pán)可以插在X钠龙、Y口渔、Z中的任意一個(gè)塔座上；
-
任何時(shí)刻都不能將一個(gè)較大的圓盤(pán)壓在較小的圓盤(pán)之上蒿涎。
用遞歸的思想來(lái)考慮漢諾塔問(wèn)題
漢諾塔問(wèn)題的實(shí)現(xiàn)步驟：
- 先將前n-1(63)個(gè)盤(pán)子移動(dòng)到Y(jié)上哀托，確保大盤(pán)在小盤(pán)下；
- 再將最底下的第n(64)個(gè)盤(pán)子移動(dòng)到Z上劳秋；
- 最后將Y上的n-1(63)個(gè)盤(pán)子移動(dòng)到Z上仓手。
那么問(wèn)題就化解為解決一下兩個(gè)問(wèn)題：
- 問(wèn)題一：將X上的n-1(63)個(gè)盤(pán)子借助Z移動(dòng)到Y(jié)上；
- 問(wèn)題二：將Y上的n-1(63)個(gè)盤(pán)子借助X移動(dòng)到Z上玻淑。
解決這兩個(gè)步驟的思路相同：
問(wèn)題一：
- 先將前n-2(62）個(gè)盤(pán)子移動(dòng)到Z上嗽冒，確保大盤(pán)在小盤(pán)下；
- 再將最底下的第n-1(63)個(gè)盤(pán)子移動(dòng)到Y(jié)上补履；
- 最后將Z上的n-2(62)個(gè)盤(pán)子移動(dòng)到Y(jié)上添坊。
問(wèn)題二： - 先將前n-2(62）個(gè)盤(pán)子移動(dòng)到X上，確保大盤(pán)在小盤(pán)下箫锤；
- 再將最底下的第n-1(63)個(gè)盤(pán)子移動(dòng)到Z上贬蛙；
- 最后將Z上的n-2(62)個(gè)盤(pán)子移動(dòng)到Y(jié)上雨女。
得出相同的規(guī)律：這其實(shí)就是一個(gè)遞歸問(wèn)題。
代碼：
void hanoi(int n, char x, char y, char z){
if (n == 1) // 只有一層的情況
printf("%c --> %c\n", x, z);
else{
hanoi(n - 1, x, z, y); // 將 n-1 個(gè)盤(pán)子從 x 借助 z 移動(dòng)到 y 上
printf("%c --> %c\n", x, z); // 將第 n 個(gè)盤(pán)子從 x 移動(dòng)到 z 上
hanoi(n-1, y, x, z); // 將 n-1 個(gè)盤(pán)子從 y 借助 x 移動(dòng)到 z 上
}
}
測(cè)試代碼：
int main(int argc, const char * argv[]) {
int n;
printf("請(qǐng)輸入漢諾塔的層數(shù)：");
scanf("%d", &n);
printf("移動(dòng)的步驟如下：\n");
hanoi(n, 'X', 'Y', 'Z');
return 0;
}
八皇后問(wèn)題遞歸解法
八皇后問(wèn)題是一個(gè)以國(guó)際象棋為背景的問(wèn)題：如何能夠在 8×8 的國(guó)際象棋棋盤(pán)上放置八個(gè)皇后阳准，使得任何一個(gè)皇后都無(wú)法直接吃掉其他的皇后氛堕？為了達(dá)到此目的，任兩個(gè)皇后都不能處于同一條橫行野蝇、縱行或斜線上讼稚。
用遞歸解決八皇后問(wèn)題的代碼
#include <stdio.h>
int count = 0;
/**
* 判斷是否有危險(xiǎn)
*/
int notdanger(int row,int j,int (*chess)[8]){
int i,k;
//判斷列方向
for(i=0;i<8;i++){
if(*(*(chess+i)+j)==1) return 0; //這一列已存在皇后
}
//判斷左上方
for(i=row,k=j;i>=0&&k>=0;i--,k--){
if(*(*(chess+i)+k)==1) return 0; //左上方已存在皇后
}
//判斷右下方
for(i=row,k=j;i<8&&k<8;i++,k++){
if(*(*(chess+i)+k)==1) return 0; //右下方已存在皇后
}
//判斷左下方
for(i=row,k=j;i<8&&k>=0;i++,k--){
if(*(*(chess+i)+k)==1) return 0; //左下方已存在皇后
}
//判斷右上方
for(i=row,k=j;i>=0&&k<8;i--,k++){
if(*(*(chess+i)+k)==1) return 0; //右上方已存在皇后
}
return 1;
}
/**
* 參數(shù)row：起始行
* 參數(shù)n: 列數(shù)
* 參數(shù)(*chess)[8]：指向棋盤(pán)每一行的指針
*/
void eightqueen(int row,int n,int (*chess)[8]){
int chess2[8][8],i,j; // 臨時(shí)棋盤(pán)
for(i=0;i<8;i++){
for(j=0;j<8;j++){
chess2[i][j] = chess[i][j]; // 臨時(shí)棋盤(pán)賦值給棋盤(pán)
}
}
if(row == 8){
printf("第%d種：\n",count + 1);
for(i=0;i<8;i++){
for(j=0;j<8;j++){
printf("%d ",*(*(chess2+i)+j));
}
printf("\n");
}
count ++;
}else {
//判斷這個(gè)位置是否有危險(xiǎn)
//如果有危險(xiǎn)，那繼續(xù)往下
for(j=0;j<n;j++){
if(notdanger(row,j,chess)){ //判斷是否危險(xiǎn)
for(i=0;i<8;i++){ // 不危險(xiǎn)
*(*(chess2+row)+i)=0;
}
*(*(chess2+row)+j)=1;
eightqueen(row+1,n,chess2);
}
}
}
}
int main(int argc, const char * argv[]) {
int chess[8][8]; // 8*8的棋盤(pán)
int i,j;
//初始化棋盤(pán)為0
for(i=0;i<8;i++){
for(j=0;j<8;j++){
chess[i][j]=0;
}
}
eightqueen(0,8,chess);//從第0行開(kāi)始依次以行為單位遍歷
printf("\n總共有 %d 種解決辦法绕沈！\n\n",count);
return 0;
}
