遞歸就是函數間接的調用自己， 它的實現基于函數參數傳遞的棧機制， 每次遞歸遞歸調用都會多一個棧幀——和簡單的函數調用并沒有什么不同 (都是使用了調用棧)。調用自己和調用其它函數并沒有本質的區別， 都是建立新棧幀， 傳遞參數并修改當前代碼行。在函數體執行完畢后刪除棧幀， 處理返回值并修改當前代碼行。
遞歸在數據結構中占有很重要的，特別是， 樹和圖的建立， 和遍歷。 使用遞歸能使代碼更清晰， 更簡潔， 但是調試時會很麻煩， 所以， 對于遞歸要熟練應用且小心應用。
下面是幾個簡單的應用舉例：
<1>
Fibonacci數列 1 n = 0， 1
F(n) =
F(n-1) + F(n-2) n>=2
1 #include<iostream> 2 using namespace std; 3 4 int fibonacci(int n) 5 { 6 if(n<=1) return 1; 7 return fibonacci(n-1) + fibonacci(n-2); 8 } 9 10 int main() 11 { 12 int n; 13 while(scanf("%d", &n)!=EOF) 14 { 15 n = fibonacci(n); 16 printf("%d\n", n); 17 } 18 return 0; 19 }
//較優化的Fibonacci數列。 #include<cstdio> using namespace std; int a[100]; int Fib(int n) { if (n <= 1) return a[1]=1; else { a[n] = Fib(n - 1) + Fib(n - 2); return a[n]; } } int main() { int n; while(scanf("%d", &n)!=EOF) { n = Fib(n); printf("%d\n", n); } return 0; }
此題 有更快的解法， 用矩陣快速冪求解 構造2*2 的矩陣{ 1， 1， 1， 0}； 這個代碼后面在矩陣的應用中會給出。
其實斐波那契數列是一個十分有趣的數列， a[n+2] - a[n+1] - a[n] = 0 。 如果我們令 q^(n+2) - q^(n+1) - q^n = 0。
可以解出 q 的兩個值， 然后 利用這兩個值，和前兩項列出一個二元一次方程，解出系數。這樣就求出了 斐波那契數列的通項！
斐波那契數列還具有周期性， 具有一些循環性的性質。
<2>. 漢諾塔問題， 有三個鋼針， A， B， C， A 上有n個圓盤， 大的在下面， 小的在上面， 你可以借借助B針， 把A針上的圓盤移到C盤上，（任何時候較大盤都不能放在較小盤上）， 對于一個不太大的n（據說n等于64時， 每秒移動一次， 宇宙會在完成的那一瞬間毀滅， 嘿嘿！！）， 請給出移動次數最少的解決方案！
1 #include<stdio.h> 2 3 void Move(int n, char A, char B) 4 { 5 printf("Move disk %d from %c to %c\n", n, A, B); 6 } 7 8 void hanoi(int n, char A, char B, char C) 9 { 10 if(n==1) Move(1, A, C); 11 else 12 { 13 hanoi(n-1, A, C, B); 14 Move(n, A, C); 15 hanoi(n-1, B, A, C); 16 } 17 } 18 19 int main() 20 { 21 int n; 22 while(scanf("%d", &n)!=EOF, n) 23 { 24 hanoi(n, 'A', 'B', 'C'); 25 } 26 return 0; 27 }
程序解釋： 當n==1時， 很顯然， 直接把它從A針上移動到C針上就好了。即： if（n==1） Move（1， A， C）；
當 n > 1時， 我們可以這樣考慮， 我們可以把A針上面的 n-1個盤借助C針， 移動到B針上，然后把A針上的盤移動到C盤上。
然后再把B盤上的n-1個盤， 借助于A盤， 移動到C盤。
很顯然， 移動n個盤的問題就轉化成了移動n-1個盤的問題。依次類推， 此問題最終變成求解移動一個盤的問題。
<3>并非一切遞歸函數都能用非遞歸方式定義， 也就是說， 有些函數只能用遞歸的形式進行定義或描述。 例如 雙遞歸函數——Ackerman函數。當一個函數以及它的一個變量是由函數自身定義時， 稱這個函數是雙遞歸函數。 Acerman函數 A(n， m)有兩個獨立的整變量m>=0和n>=0, 其定義如下：
A（1， 0） = 2
A(0， m) = 1 m>=0
A(n, 0) = n + 2 n>=2
A(n, m) = A(A(n-1, m), m-1) n, m >=1 。 這個函數增長快的驚人。
1 #include<cstdio> 2 #include<cstring> 3 using namespace std; 4 5 typedef long long LL; 6 LL ans = 0; 7 8 LL A(LL n, LL m) 9 { 10 if(n==1&&m==0) return 2; 11 if(n==0&&m>=0) return 1; 12 if(n>=2&&m==0) return n+2; 13 return A(A(n-1, m), m-1); 14 } 15 16 int main() 17 { 18 LL a, b; 19 while(scanf("%lld%lld", &a, &b)!=EOF) 20 { 21 ans = 0; 22 ans=A(a, b); 23 printf("%lld\n", ans); 24 } 25 return 0; 26 } 27
<4> 全排列問題。1~n 的全排列。
1 #include<cstdio> 2 #include<algorithm> 3 using namespace std; 4 5 int n = 0; 6 int list[100]; 7 void perm(int list[], int k, int m) 8 { 9 int i;//顯示輸出 10 if(k>m) 11 { 12 for(i=0; i<=m; i++) 13 printf("%d", list[i]); 14 printf("\n"); 15 n++; 16 } 17 else 18 { 19 for(i=k; i<=m; i++) 20 { 21 swap(list[k], list[i]); //交換第k個數和第i個數，并把后面的數全排列 22 perm(list, k+1, m);//全排列 k+1到m 23 swap(list[k], list[i]);//第一步的逆操作，使數列保持不變，以避免重復。 24 } 25 } 26 } 27 28 int main() 29 { 30 int T; 31 while(scanf("%d", &T)!=EOF) 32 { 33 for(int i=0; i<T; i++) 34 list[i] = i+1; 35 perm(list, 2, T-1); 36 printf("total:%d\n", n); 37 } 38 return 0; 39 }
此問題有多種解法， 大都應用了遞歸方法。<algorithm>里面也包含了生成全排列的算法
next_permutation(begin, end)；
<5>整數劃分問題
如 4 可以劃分為
4
3 + 1
2+ 2 ， 2+1+1
1+1 + 1+1
在整數n的所有不同 的劃分中， 將最大加數n1 不大于 m 的劃分記作 q（n， m）。可以建立q(n， m) 的如下遞歸關系。
(1) q（n， 1） = 1 ， n>=1
加數只能全部是 1
（2）q（n， m）=q（n， n）， m>=n
m>=n, n 不可能有比n自身還大的加數。
（3） q（n， n）= 1 + q（n， n - 1）
整數n的劃分 分成 1 + （n-1） 和 q（n， n-1）兩種情況
(4) q（n， m） = q (n，m-1) + q（n-m， m）, n>m>1
分為最大加數 n1 <=m-1時的情況， 和 n1==m時的情況。 而n1==m的情況 剛好是q（n-m，m）。（如果不太明白請結合實例理解）。
q（n, m） = 1 , n=1, m=1
q(n, m) = q(n, n) n<m
q(n, m) = 1 + q(n, n-1) n=m
q(n, m) = q(n, m-1) + q(n-m, m)
1 #include<iostream> 2 using namespace std; 3 4 int q(int n, int m) 5 { 6 if((n<1)||(m<1)) return 0; 7 if((n==1)||(m==1)) return 1; 8 if(n<m) return q(n, n); 9 if(n==m) return q(n, m-1) + 1; 10 return q(n, m-1) + q(n-m, m); 11 } 12 13 int main() 14 { 15 int a, ans = 0; 16 while(scanf("%d", &a)!=EOF) 17 { 18 ans=q(a, a); 19 printf("%d\n", ans); 20 } 21 return 0; 22 }
此問題也有另外一種特別巧妙的解決辦法： 生成函數。
《5》遞歸求最大公因數和最小公倍數
1 #include<iostream> 2 using namespace std; 3 4 //遞歸， 求最大公因數 5 int gcd(int a, int b) 6 { 7 return b ? gcd(b, a%b) : a; 8 } 9 10 int main() 11 { 12 int n, m; 13 while(scanf("%d%d", &n, &m)!=EOF) 14 { 15 printf("%d\n", gcd(n, m)); 16 } 17 return 0; 18 }
1 #include<iostream> 2 using namespace std; 3 4 //遞歸， 求最小公倍數 5 int gcd(int a, int b) 6 { 7 return b ? gcd(b, a%b) : a; 8 } 9 10 int main() 11 { 12 int n, m; 13 while(scanf("%d%d", &n, &m)!=EOF) 14 { 15 printf("%d\n", n/gcd(n, m)*m); 16 } 17 return 0; 18 }
《6》半數集問題
(1) n set(n)；
(2) 在n的左邊加上一個自然數，但該自然數不能超過最近添加的數的一半；
(3) 按此規則進行處理，直到不能再添加自然數為止。
例如，set(6)={6，16，26，126，36，136}。
半數集set(6)中有6個元素。
對于給定的自然數n，編程計算半數集set(n)中的元素個數。
設set(n)中的元素個數為 F（n） ，則顯然有：
F（n） = 1 + F（1） + F（2） + …… + F(n/2)
|
第一次半數集 |
112 |
212 |
312 |
412 |
512 |
612 |
|
忽略原始數字12 |
1 |
2 |
3 |
4 |
5 |
6 |
|
|
|
12 |
13 |
14 24，124 |
15 25，125 |
16 26，126 36，136 |
以 n 為12 為例！
1 #include<iostream> 2 #include<cstring> 3 using namespace std; 4 5 int a[1005]; 6 7 int comp(int n)//記憶化搜索 8 { 9 int ans = 1; 10 if(a[n]>0) return a[n]; 11 for(int i=1; i<=n/2; i++) 12 ans += comp(i); 13 a[n] = ans; 14 return ans; 15 } 16 17 int main() 18 { 19 memset(a, 0, sizeof(a)); 20 int n; 21 cin>>n; 22 cout<<comp(n)<<endl; 23 return 0; 24 }
《7》http://acm.hdu.edu.cn/showproblem.php?pid=1297（遞歸+高精度加法）
#include<iostream> #include<cstdio> using namespace std; int main() { int a[1001][101] = {0}; a[0][1] = 1; a[1][1] = 1; a[2][1] = 2; a[3][1] = 4; for(int i=4; i<1001; i++) for(int j=1; j<101; j++) { a[i][j] += a[i-1][j] + a[i-2][j] + a[i-4][j]; a[i][j+1] += a[i][j]/1000000; a[i][j] %= 1000000; } int n; while(scanf("%d", &n)!=EOF) { int k = 100; while(!a[n][k]) k--; printf("%d", a[n][k]); for(int i=k-1; i>0; i--) printf("%06d", a[n][i]); printf("\n"); } return 0; }
遞歸方程： ,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,（見代碼和分析過程）
分析過程：
設：F(n)表示n個人的合法隊列，則：
按照最后一個人的性別分析，他要么是男，要么是女，所以可以分兩大類討論：
1、如果n個人的合法隊列的最后一個人是男，則對前面n-1個人的隊列沒有任何限制，他只要站在最后即可，所以，這種情況一共有F(n-1);
2、如果n個人的合法隊列的最后一個人是女，則要求隊列的第n-1個人務必也是女生，這就是說，限定了最后兩個人必須都是女生，這又可以分兩種情況：
2.1、如果隊列的前n-2個人是合法的隊列，則顯然后面再加兩個女生，也一定是合法的，這種情況有F(n-2);
2.2、但是，難點在于，即使前面n-2個人不是合法的隊列，加上兩個女生也有可能是合法的，當然，這種長度為n-2的不合法隊列，不合法的地方必須是尾巴，就是說，這里說的長 度是n-2的不合法串的形式必須是“F(n-4)+男+女”，這種情況一共有F(n-4).
怒切此題：
當草灘小恪求出這個遞推方程后， 很是得意，，， 于是他便屁顛屁顛的去切這道題去啦。 然而， wang一直陪伴著他。 仔細想一下，Fibonacci數列就已增長的很快， 而且這個數列增長的比Fibonacci數列更快。 所以第1000項會非常的大。所以不用高精度是不行的。
《8》Big String
把A接在B的后面構成新的字符串C。
例如，A＝“^__^”，B＝“T.T”，則C＝BA＝“T.T^__^”。
令A＝B，B＝C，如上例所示，則A＝“T.T”，B＝“T.T^__^”。
文章列表
留言列表
