遞歸和分治思想及其應用

目錄

• 遞歸和分治思想
• 一些實例
  • 逆序輸出字符串
  • 查找數組元祖是否存在
  • 漢諾塔問題
  • 八皇后問題
• 更多：

遞歸和分治思想

如果可以使用迭代，盡量別使用遞歸。由編譯原理可以知道，每次自調用的時候，計算機都需要保存在調用，浪費時間空間。當然，迭代是當我們知道循環次數的時候。而當我們不知道循環次數，比如說對于文件夾和文件進行遍歷，不知道深度的情況下，我們就需要遞歸來實現。

顯然，遞歸是先解決小的問題，這種思想是分治思想。根據具體需求，來決定是否使用遞歸。

遞歸要注意：

• 結構是選擇結構，而迭代是循環結構
• 必須有基線條件和遞歸條件，防止出現死循環
• 如果知道循環次數的話，盡量使用遞歸
• 對于某些編程式函數，有對于尾遞歸的迭代優化
• 遞歸邏輯更容易理解

一些實例

逆序輸出字符串

#include<iostream>
using namespace std;void print(){char a;cin>>a;if(a!='#') print(); // 不是停止符，先自調用 if(a!='#') cout<<a; //在回來的時候，打印自己的字符 
}
int main(){print();return 0;
}

查找數組元祖是否存在

很多時候我們需要查找一個數組中是否有一個元素。如果使用迭代，肯定十分簡單，時間復雜度為O(n)。

此時，如果使用分而治之的思想，我們可以使用二分法來進行查找。不論多大的數據，時間復雜度顯著降低為O(log_2 n)。也就是說一個大小為123456789的數組，使用迭代，我們需要123456789個時間單位。但是二分法只需要27次。

實現思路：

1. 首先轉化的思想對數組進行排序。如果不排序，那么low和high就沒有意義了。
2. 再用迭代進行二分

#include<iostream>
#include<algorithm>
using namespace std;
const int SIZE = 5;
const int NONE = -1;
//二分查找并且返回element的位置，沒查找到則返回NONE
template<class T>
int BinFind(T *arr,int low,int high,T elem){  int mid;if(low>high)return NONE;else{mid = (low+high)/2;if(arr[mid] == elem)return mid;else if(elem>arr[mid])return BinFind(arr,mid+1,high,elem);elsereturn BinFind(arr,low,mid-1,elem);}
}
int main(){int *arr = new int [SIZE];cout<<"請輸入"<<SIZE<<"個數據："; for(int i=0;i<SIZE;++i)cin>>arr[i];sort(arr,arr+SIZE);int elem;cout<<"輸入您要查找的數據："<<endl;cin>>elem; int index = BinFind(arr,0,SIZE-1,elem);if (index+1)cout<<"含有這個數據\n";elsecout<<"不含有這個數據";return 0;
}

漢諾塔問題

首先我們假設需要移動64層，那么思路如下（附截圖）：

此時，需要解決兩個問題（附截圖）：

一直這樣類推，知道最后從begin(開始柱子)->end(目標柱子)。

按照第一張截圖，我們可以寫出來函數里面else的遞歸部分。并且，每次輸出的時候，就對應著思路里面的移動（而不是分治），此時step步數需要加+。

#include<iostream>
#include<algorithm>
using namespace std;
void Hanoi(int num,char begin,char by,char end,int &step){if(num==1){cout<<begin<<"-->"<<end<<endl;++step;}else{Hanoi(num-1,begin,end,by,step);cout<<begin<<"-->"<<end<<endl;++step;Hanoi(num-1,by,begin,end,step);}
}
int main(){int step = 0;int num;cout<<"漢諾塔層數是: ";cin>>num;Hanoi(num,'X','Y','Z',step);cout<<"一共有："<<step<<"步數"<<endl; return 0;
}

八皇后問題

在8×8格的國際象棋上擺放八個皇后，使其不能互相攻擊，即任意兩個皇后都不能處于同一行、同一列或同一斜線上，問有多少種擺法。正規的方法是遞歸，如果不考慮效率，這里采用遞歸實現。假設從第一行開始，每一行都找到符合條件的一個位置，而條件就是新的一行的新位置符合要求，以此類推，就可以寫出來遞歸函數。

#include<iostream>
using namespace std;const int Q_NUM = 8;
int queens[Q_NUM][Q_NUM] = {0};
int RESULT = 0;void print(){for(int i=0;i<Q_NUM;++i){for (int j=0;j<Q_NUM;++j)cout<<queens[i][j]<<" ";cout<<endl;}cout<<endl<<endl;
}
bool IfQueen(int row,int col){if(row==0){//當第一行時候，隨便擺放 queens[row][col] = 1;return true;}/**************其他時候，需要考慮上面的同一列、左上角斜線、右上角斜線，以下分別實現*****/ for(int i=0;i<row;++i)if(queens[i][col]==1)return false;for (int i=row-1,j = col-1;i>=0 && j>=0;--i,--j)if(queens[i][j]==1)return false;for(int i=row-1,j=col+1;i>=0 && j<Q_NUM;--i,++j)if(queens[i][j]==1)return false;/******當所有情況都滿足********/queens[row][col] = 1;return true;
}
void Queen(int row){if(row==Q_NUM){ //注意row是從0開始到Q_NUM-1結束。這樣當row==Q_NUM時，已經排完所有情況 ++RESULT;   //這樣當row==Q_NUM時，已經排完所有情況，進行輸出就可以了。 print();return ;} for(int i=0;i<Q_NUM;++i){ //i代表列數 if(IfQueen(row,i)) //如果row行i列可以放得話，判斷下一行 Queen(row+1);queens[row][i] = 0; //重置為0，防止下次結果干擾 }
}int main(){Queen(0);cout<<"一共"<<RESULT<<"種擺法\n";return 0;
}

---

更多：

毫無疑問，遞歸以及分治思想還有很多用法：斐波那契數列、快速排序、文件查找、字典樹的建立等等。理論上遞歸可以解決任何問題，而作為我們只需要提供思路，其他的交給計算機解決。所以聽人說過計算機最適合解決遞歸問題。但是，有利有弊，遞歸同樣會消耗更多的內存。在初步實現階段，將大問題分而治之，分裝成遞歸函數，還是邏輯代碼化的最佳表達。

---

歡迎進一步交流本博文相關內容：

博客園地址 : http://www.cnblogs.com/AsuraDong/

CSDN地址 : http://blog.csdn.net/asuradong

也可以致信進行交流 : xiaochiyijiu@163.com

歡迎轉載 , 但請指明出處 ?:??)

---