“奇技淫巧” 話(huà)遞歸
“To Iterate is Human, to Recurs，Divine.” ---L. Peter Deutsch
“迭代是人，遞歸是神” 第一次見(jiàn)有人這樣說(shuō)，讓我受傷的心得到些許安慰......
最近在琢磨算法，又見(jiàn)遞歸！ 這是個(gè)繞不過(guò)去的坎！ 當(dāng)初，上大學(xué)時(shí)似懂非懂自欺欺人的蒙混過(guò)關(guān)，再次引證了那句名言：“出來(lái)混，遲早都是要還的......”。好吧，那就直面它！于是搜遍海內(nèi)外，加上日思夜想，被這“奇技淫巧”折魔得真掉了不少頭發(fā)（主要是8皇后問(wèn)題~）。
大神王垠在談程序語(yǔ)言最精華的原理時(shí)提到遞歸，并說(shuō)遞歸比循環(huán)表達(dá)能力強(qiáng)很多，而且效率幾乎一樣?。?！沒(méi)有一定的內(nèi)力，估計(jì)你很難理解他這句話(huà)，當(dāng)然他說(shuō)得沒(méi)錯(cuò)！
務(wù)必要弄懂弄透它！抱著一股不服的擰勁和不死的初心，蒙生了收集所有經(jīng)典遞歸案例寫(xiě)法作一匯總的想法。
如果您不能像大神一樣一眼就看穿其本質(zhì)并熟練的運(yùn)用它（不自欺），不妨一起來(lái)領(lǐng)略領(lǐng)略這“奇技淫巧”的各案之美， 由簡(jiǎn)到難，慢慢的你一定會(huì)覺(jué)得它越來(lái)越美！
如發(fā)現(xiàn)還有文中沒(méi)收集到的經(jīng)典例子，歡迎補(bǔ)充添加，以澤后人，算積功德一件~
作者承諾：所有代碼都經(jīng)過(guò)測(cè)試，所有評(píng)論都是算法在腦中真真切切過(guò)了一遍之后的切膚反饋。
經(jīng)典遞歸例子匯總與點(diǎn)評(píng)：
數(shù)學(xué)定義：
1 //求N！ 2 long int F( long int N) 3 { 4 if(N==0) 5 return 1; 6 if(N>0) 7 return N*F(N-1); 8 }
1 2 int main( int argv, char** argc){ 3 long int N; 4 cin>>N; 5 cout<<F(N)<<endl; 6 }
對(duì)著數(shù)學(xué)公式寫(xiě)代碼是不是很容易？這個(gè)用遞歸比循環(huán)更易寫(xiě)，更容易理解！閉著眼睛，想想循環(huán)怎么寫(xiě)？...是不是有點(diǎn)啰嗦~？
這個(gè)是編程用循環(huán)的入門(mén)思維，用for語(yǔ)句太簡(jiǎn)單，如果讓以遞歸方式寫(xiě)，很多人可能又會(huì)卡一會(huì)兒了。但是如果你把它按數(shù)學(xué)公式的方式定義一下，和N!一樣，遞歸就好寫(xiě)多了！
數(shù)學(xué)定義：
1 int Sum(int N) 2 { 3 4 if(N==1) 5 return 1; 6 if(N>1) 7 return N+Sum(N-1); 8 else 9 return 0; 10 } 11
按數(shù)學(xué)公式寫(xiě)代碼，是不是讓生活更美好！~
3. Fibonacci數(shù)列，F(n)=F(n-1)+F(n-2)
數(shù)學(xué)定義：
1 int Fibonacci(int N) 2 { 3 if(N==1||N==2) 4 return 1; 5 if(N>2) 6 return Fibonacci(N-1)+Fibonacci(N-2); 7 else 8 return 0; 9 }
這個(gè)遞歸很好寫(xiě)，如果閉眼用循環(huán)寫(xiě)，估計(jì)要點(diǎn)時(shí)間，有幾個(gè)變量需要耐心引入。
始祖毆基里德給出了輾轉(zhuǎn)相除的遞歸原則，知道這個(gè)寫(xiě)起來(lái)就容易多了，但理解天才的想法是如何得來(lái)的還是要費(fèi)點(diǎn)腦子的。
我曾試圖去網(wǎng)上找找它的數(shù)學(xué)定義，很遺憾大都是些拗口的文字描述，代碼反而容易理解一些。
1 int GCD(int a, int b) 2 { 3 if(a>0&&b>0){ 4 if(a%b==0){ 5 return b; 6 }else{ 7 return GCD(b,a%b); 8 } 9 } 10 }
于是從代碼中反推出其數(shù)學(xué)公式~:
真是佩服那個(gè)出題的和尚，高僧！??！當(dāng)然會(huì)解題的也是高人。
如上圖，要把A中所有圓盤(pán)經(jīng)B輔助移到C，移動(dòng)過(guò)程中，要求園盤(pán)之上始終只能是比其小的圓盤(pán)。規(guī)則描述不復(fù)雜，但怎么把它轉(zhuǎn)化成數(shù)學(xué)定義呢？懵！先從code入手？
1 void Hanoi(int N, char source, char auxiliary, char target) 2 { 3 4 if(N==1){ 5 cout<<"Move disk: "<<N<<" from "<<source<<" to "<<target<<endl; 6 }else { 7 Hanoi(N-1,source,target,auxiliary); 8 cout<<"Move disk: "<<N<<" from "<<source<<" to "<<target<<endl; 9 Hanoi(N-1,auxiliary,source,target); 10 } 11 } 12 13 Hanoi(5,'A','B','C');
還是沒(méi)法寫(xiě)成數(shù)學(xué)恒等式，為什么？因?yàn)樵谄溥f歸終點(diǎn)不再是返回值以供調(diào)用者使用，而是執(zhí)行了一次操作，依次返回過(guò)程中都是再執(zhí)行一次操作，不是數(shù)量表達(dá)關(guān)系，因此較難用數(shù)學(xué)定義語(yǔ)言描述這類(lèi)問(wèn)題。
不用遞歸，夠你死一丟腦細(xì)胞的?；匚臄?shù)是指前后對(duì)稱(chēng)的數(shù)，如（1，121，12321等）。
假設(shè)數(shù)字都以字符串的形式存儲(chǔ)，為了大數(shù)判斷和一般的通用回文判斷，采用這種形式
1 bool isPali(string S, int startindex) 2 { 3 if(S.size()==1||startindex>=S.size()-1-startindex){ 4 return true; 5 } 6 if(S[startindex]!=S[S.size()-1-startindex]){ 7 return false; 8 } 9 10 return isPali(S, startindex+1); 11 } 12 13 int main(){ 14 string S; 15 cin>>S; 16 cout<<isPali(S,0)<<endl; 17 }
試試把它數(shù)學(xué)定義式寫(xiě)出來(lái)：
老祖宗蠻厲害，但這樣說(shuō)，似乎有點(diǎn)類(lèi)我黨自夸之嫌~
把它轉(zhuǎn)化成(row,col)直角形式如下
要得到數(shù)字的值, 遞歸算法如下：
1 int GetVOfYangHui(int row, int col) 2 { 3 if(col<=row && col>=0){ 4 if(col==0||row==col){ 5 return 1; 6 }else{ 7 return GetVOfYangHui(row-1,col-1)+GetVOfYangHui(row-1,col); 8 } 9 }else { 10 return 0; 11 } 12 }
試試把它數(shù)學(xué)定義式寫(xiě)出來(lái)：
讓你悶頭寫(xiě)一個(gè)，是不是也有點(diǎn)難度啊？
主框架用遞歸的思維很簡(jiǎn)單，稍麻煩一點(diǎn)的是分割DPart，需要用到一點(diǎn)編程的技巧。
1 int DPart(int* A, int start, int end) 2 { 3 int key=A[end]; 4 int index=end; 5 while(start<end){ 6 7 while(A[start]<key){ start++;} 8 while(A[end]>=key){end--;} 9 if(start<end){ swap(A[start],A[end]);} 10 else{ 11 break; 12 } 13 14 } 15 swap(A[start],A[index]); 16 return start; 17 } 18 19 void QuickSort(int* A, int start, int end) 20 { 21 if(start>end||start<0||end<0){ 22 return; 23 } else { 24 int index=DPart(A,start,end); 25 QuickSort(A,start,index-1); 26 QuickSort(A,index+1,end); 27 } 28 29 } 30
主框架用遞歸的思維也很簡(jiǎn)單，關(guān)鍵在寫(xiě)Merge時(shí)，需要用到一點(diǎn)點(diǎn)編程的技巧。
1 void Merge(int A[], int low, int mid, int high) 2 { 3 int n1= mid-low+1; 4 int n2= high-mid; 5 6 int L[n1],R[n2]; 7 for(int i=0;i<n1;i++) 8 L[i]=A[i+low]; 9 10 for(int j=0;j<n2;j++) 11 R[j]=A[j+mid+1]; 12 13 int i=0,j=0,k=low; 14 15 while(i!=n1 && j!= n2) 16 { 17 if(L[i] <= R[j]) 18 A[k++] = L[i++]; 19 else 20 A[k++] = R[j++]; 21 } 22 23 while(i < n1) 24 A[k++] = L[i++]; 25 while(j < n2) 26 A[k++] = R[j++]; 27 28 } 29 30 void MergeSort(int A[], int low, int high) 31 { 32 if(low<high){ 33 int mid = (low+high)/2; 34 MergeSort(A,low,mid); 35 MergeSort(A,mid+1,high); 36 37 Merge(A,low,mid,high); 38 } 39 }
這個(gè)可算是搞數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)的人把遞歸思想發(fā)揮到極致的經(jīng)典案例吧？
這部分code 有些冗長(zhǎng)，為了完整性，還是把它全貼出來(lái)。主要目的是體會(huì)其前，中，后序遍歷的遞歸寫(xiě)法。為了建樹(shù)方便，我們以數(shù)據(jù)輸入順序按層序方式建樹(shù)，它需要用到隊(duì)列技巧（與遞歸無(wú)關(guān)，暫不討論），同時(shí)加入一個(gè)層序遍歷方法來(lái)驗(yàn)證輸入。注意層序遍歷很難用遞歸方法實(shí)現(xiàn)，我思考了很久都沒(méi)有結(jié)果，如果你有想到，一定告知一聲，萬(wàn)謝！（mathmad@163.com)
1 #include <iostream> 2 #include <queue> 3 #include <stdio.h> 4 5 using namespace std; 6 7 struct Node { 8 int data; 9 Node* left; 10 Node* right; 11 }; 12 13 class Btree 14 { 15 public: 16 Btree(); 17 ~Btree(); 18 19 Node *createNode(int data); 20 Node *GetRoot(); 21 void insert(Node *newNode); 22 void destroy_tree(); 23 void levOrder(Node *root); 24 void preOrder(Node *root); 25 void midOrder(Node *root); 26 void posOrder(Node *root); 27 private: 28 void destroy_tree(Node *leaf); 29 Node *root; 30 queue<Node *> q; 31 }; 32 33 Btree::Btree() 34 { 35 root=NULL; 36 } 37 Btree::~Btree() 38 { 39 if(root!=NULL){ 40 destroy_tree(root); 41 } 42 } 43 44 void Btree::destroy_tree(Node *leaf) 45 { 46 if(leaf!=NULL) 47 { 48 destroy_tree(leaf->left); 49 destroy_tree(leaf->right); 50 delete leaf; 51 } 52 } 53 Node* Btree::createNode(int data) 54 { 55 Node* n=new Node; 56 n->left=NULL; 57 n->right=NULL; 58 n->data=data; 59 return n; 60 } 61 Node* Btree::GetRoot() 62 { 63 return root; 64 } 65 66 void Btree::insert(Node *newnode) 67 { 68 if(NULL==root){ 69 root=newnode; 70 q.push(root); 71 }else{ 72 Node *f=q.front(); 73 if(f->left&&f->right){q.pop(); f=q.front();} 74 if(!f->left){ f->left=newnode;} 75 else if(!f->right){ f->right=newnode;} 76 q.push(newnode); 77 78 } 79 80 } 81 82 void Btree::levOrder(Node* root) 83 { 84 if(root){ 85 queue<Node*> Q; 86 Q.push(root); 87 88 while(!Q.empty()){ 89 Node *d=Q.front(); 90 cout<<d->data<<" "; 91 Q.pop(); 92 if(d->left){Q.push(d->left);} 93 if(d->right){Q.push(d->right);} 94 } 95 96 } 97 98 } 99 100 void Btree::preOrder(Node* root) 101 { 102 if(NULL==root) { return;} 103 else{ 104 cout<<root->data<<" "; 105 preOrder(root->left); 106 preOrder(root->right); 107 } 108 109 } 110 111 void Btree::midOrder(Node *root) 112 { 113 if(NULL==root) { return;} 114 else{ 115 midOrder(root->left); 116 cout<<root->data<<" "; 117 midOrder(root->right); 118 } 119 120 } 121 122 void Btree::posOrder(Node *root) 123 { 124 if(NULL==root) { return;} 125 else{ 126 posOrder(root->left); 127 posOrder(root->right); 128 cout<<root->data<<" "; 129 } 130 131 } 132 133 int main( int argv, char** argc){ 134 135 Btree btree; 136 Node * newnode; 137 int data; 138 cout<<"Please input a sequences number to create a Complete Binary Tree:"<<endl; 139 140 do{ 141 cin>>data; 142 newnode=btree.createNode(data); 143 btree.insert(newnode); 144 }while(getchar()!='\n'); 145 146 cout<<"BTree Level order is:"<<endl; 147 btree.levOrder(btree.GetRoot()); 148 cout<<endl<<"Pre Order is:"<<endl; 149 btree.preOrder(btree.GetRoot()); 150 cout<<endl<<"mid Order is:"<<endl; 151 btree.midOrder(btree.GetRoot()); 152 cout<<endl<<"pos Order is:"<<endl; 153 btree.posOrder(btree.GetRoot()); 154 cout<<endl; 155 }
用g++ 編譯上述代碼(g++ BTree.cpp)，測(cè)試輸出如下：
這個(gè)有點(diǎn)難想清楚！特別是第二個(gè)swap交換！
N個(gè)元素的全排列，有高中數(shù)學(xué)基礎(chǔ)的人都易知道它總共有N!(階乘）種。若要全部打印出來(lái)，當(dāng)N>4時(shí)還是有一定麻煩，特別是當(dāng)用循環(huán)思路正面強(qiáng)攻時(shí)，會(huì)讓人陷入無(wú)盡的深淵！
下面以5個(gè)數(shù)字為例簡(jiǎn)述其原理：
假設(shè)數(shù)據(jù)集為{1, 2, 3, 4, 5}， 如何編寫(xiě)全排列的遞歸算法？
1、首先看最后兩個(gè)數(shù)4, 5。 它們的全排列為4 5和5 4, 即以4開(kāi)頭的5的全排列和以5開(kāi)頭的4的全排列。
由于一個(gè)數(shù)的全排列就是其本身，從而得到以上結(jié)果。
2、再看后三個(gè)數(shù)3, 4, 5。它們的全排列為3 4 5、3 5 4、4 3 5、4 5 3、5 4 3、5 3 4 六組數(shù)。
是以3開(kāi)頭的和4,5的全排列的組合、以4開(kāi)頭的和3,5的全排列的組合和以5開(kāi)頭的和4,3的全排列的組合，即k與(k+1,..N)的全排列組合加上k’與（k+1,...N)的全排列組合，其中k’是k與(k+1,...N)的任一置換。
網(wǎng)上通用一般描述為，設(shè)一組數(shù)p = {r1, r2, r3, ... ,rn}, 全排列為perm(p)，令pn = p - {rn}。
因此perm(p) = r1perm(p1), r2perm(p2), r3perm(p3), ... , rnperm(pn)。當(dāng)n = 1時(shí)perm(p} = r1。
為了更容易理解，將整組數(shù)中的所有的數(shù)分別與第一個(gè)數(shù)交換，這樣就總是在處理后n-1個(gè)數(shù)的全排列。（下面給出C++版, 以字符串為數(shù)據(jù)集的全排列算法）
1 #include <iostream> 2 using namespace std; 3 /* 4 全排列算法改進(jìn) 5 Author: Liang 2018-09-21 6 7 */ 8 9 int Perm(string s, int k, int m) { 10 static int n=0; 11 12 if (s!= ""&& m>=k && m<=s.size()-1 && k>=0){ 13 if(k == m){ 14 cout<<s<<endl; 15 n++; 16 }else { 17 Perm(s, k+1, m); 18 19 for(int i = k+1; i <= m; i++) { 20 swap(s[k],s[i]); 21 Perm(s, k+1, m); 22 swap(s[k],s[i]); 23 } 24 } 25 } 26 return n; 27 } 28 29 int main(){ 30 string str; 31 cin>>str; 32 int n=str.size(); 33 cout<<"total: "<<Perm(str,0,n-1)<<endl; 34 }
國(guó)際象棋棋盤(pán)上放8個(gè)皇后，問(wèn)有多少種放法（皇后的走法是水平垂直線和對(duì)角線位置可以互相攻擊） 著名的8皇后問(wèn)題，這個(gè)Gauss都只得出76種解（實(shí)際有92種），一想到這，我心理就平衡一點(diǎn)~
8 皇后問(wèn)題后演變成N皇后問(wèn)題，其中N=1時(shí)有一個(gè)解， 2，3無(wú)解，N=4時(shí)有兩個(gè)解，N=5時(shí)比N=6的解多。這說(shuō)明什么問(wèn)題？ 一個(gè)“老婆”最穩(wěn)定，2個(gè)3個(gè)后宮沒(méi)法處理，挺到4個(gè)時(shí)就會(huì)有辦法，5個(gè)“老婆”比6個(gè)老婆好處置，超過(guò)6個(gè)就是多多益善了，要想處理8個(gè)皇后，高斯都沒(méi)想清楚，可見(jiàn)多了后宮難治啊，哈哈，閑扯遠(yuǎn)了~
1 #include <iostream> 2 #include <cstdlib> 3 using namespace std; 4 #define StackSize 8 // could be set to 1, 4, 5, 6, 7,....N 5 6 int ans=0; 7 int top=-1; 8 int ColOfRow[StackSize]; //index represent the row, value is col 9 10 void Push(int col) 11 { 12 top++; 13 ColOfRow[top]=col; 14 } 15 16 void Pop() 17 { 18 top--; 19 } 20 // check put a Queen to position(row, col) is safe or not. 21 bool isPosSafe(int row, int col) 22 { 23 for(int i=0;i<row;i++) 24 { 25 //check col is ok, row is increase invoke, same is impossible 26 if(col==ColOfRow[i]){ 27 return false; 28 } 29 // Y=kX+b, k=1 or k=-1, the Queen will attack each other 30 if(abs(col-ColOfRow[i])==(row-i)){ 31 return false; 32 } 33 } 34 return true; 35 } 36 37 void PrintBoard() 38 { 39 cout<<"NO."<<ans<<":"<<endl; 40 for(int i=0;i<StackSize;i++) 41 { 42 for(int j=0;j<ColOfRow[i];j++) 43 cout<<"_ "; 44 cout<<"Q"; 45 for(int j=StackSize-1;j>ColOfRow[i];j--) 46 cout<<" _"; 47 cout<<endl; 48 } 49 cout<<endl; 50 } 51 // Should be start from 0 row, since the start point will impact future steps desision 52 void PlaceQueen(int row) 53 { 54 for (int col=0;col<StackSize;col++) 55 { 56 Push(col); 57 if (isPosSafe(row,col)) 58 { 59 if (row<StackSize-1) 60 PlaceQueen(row+1); 61 else 62 { 63 ans++; 64 PrintBoard(); 65 } 66 } 67 Pop(); 68 } 69 } 70 71 72 int main() 73 { 74 // Since Recursion invoke, start point should be 0, the first row 75 PlaceQueen(0); 76 cout<<"the total solutions is:"<<ans<<endl; 77 return 0; 78 } 79 80
沒(méi)有數(shù)學(xué)遞歸公式，循環(huán)怕是很難搞清
posted on 2018-09-23 02:16 L,wang 閱讀(805) 評(píng)論(0) 收藏 舉報(bào)
浙公網(wǎng)安備 33010602011771號(hào)