遞歸C++

一、遞歸簡介

自己調用自己

二、遞歸寫法

2.1 寫法介紹

先寫出問題的遞推公式

遞歸部分的邊界條件就是遞推公式中的邊界條件

遞歸部分的主體部分就是遞推公式中的主體部分

2.2 實例

（1）題目

例如：求n！。

（2）分析

遞歸公式為 f(n)=f(n-1)*n f(1)=1;

對應的遞歸：

 1 /*
 2     階乘遞歸 
 3     遞歸公式為 f(n)=f(n-1)*n f(1)=1;
 4     遞歸部分的邊界條件就是遞推公式中的邊界條件 f(1)=1
 5     遞歸部分的主體部分就是遞推公式中的主體部分 f(n)=f(n-1)*n
 6 */
 7 int factorial_Recursion(int n){
 8     if(n==1) return 1;
 9     else return factorial_Recursion(n-1)*n;
10 }

（3）完整代碼

 1 #include <iostream>
 2 using namespace std;
 3 
 4 int factorial(int n);
 5 int factorial_Recursion(int n);
 6 
 7 /*
 8     階乘非遞歸 
 9 */
10 int factorial(int n){
11     int ans=1;
12     for(int i=1;i<=n;i++){
13         ans*=i;
14     }
15     return ans;
16 }
17 
18 /*
19     階乘遞歸 
20     遞歸公式為 f(n)=f(n-1)*n f(1)=1;
21     遞歸部分的邊界條件就是遞推公式中的邊界條件 f(1)=1
22     遞歸部分的主體部分就是遞推公式中的主體部分 f(n)=f(n-1)*n
23 */
24 int factorial_Recursion(int n){
25     if(n==1) return 1;
26     else return factorial_Recursion(n-1)*n;
27 }
28 
29 int main(){
30     int ans;
31     //ans=factorial(5); 
32     ans=factorial_Recursion(5); 
33     printf("%d\n",ans);
34     return 0;
35 } 

（4）代碼結果

120

三、遞歸實例

3.1 輾轉相除法求公約數

遞推公式：f(a,b)=f(b,a%b) b!=0;

代碼：

 1 #include <iostream>
 2 using namespace std;
 3 
 4 void exchange(int &a,int &b); 
 5 int commonDivisor(int a,int b);
 6 int commonDivisor_Recursion(int a,int b);
 7 
 8 /*
 9     交換a和b兩個數的值 
10 */
11 void exchange(int &a,int &b){
12     a=a^b;
13     b=a^b;
14     a=a^b; 
15 } 
16 
17 /*
18     非遞歸輾轉相除法求公約數：
19     用輾轉相除法的時候要保證a大於等於b 
20 */
21 int commonDivisor(int a,int b){
22     if(b>a)    exchange(a,b);
23     int tmp=a%b;
24     while(tmp){
25         a=b;
26         b=tmp;
27         tmp=a%b;
28     }
29     return b;
30 } 
31 
32 /*
33     遞歸輾轉相除法求公約數：
34     用輾轉相除法的時候要保證a大於等於b 
35     遞推公式：f(a,b)=f(b,a%b) b!=0;
36     邊界條件為： b!=0
37     遞歸主體為： f(a,b)=f(b,a%b)
38 */
39 int commonDivisor_Recursion(int a,int b){
40     if(a%b==0) return b;
41     else   commonDivisor_Recursion(b,a%b);
42 }
43 
44 int main(){
45     int ans;
46     //ans=commonDivisor(15,9);
47     ans=commonDivisor_Recursion(15,9);
48     printf("%d\n",ans);
49     return 0;
50 } 

代碼結果：

3

3.2 判斷和相等

題目：

已知一個一維數組a[1...n]和一個確定的數m，判斷能否使數組a中的任意幾個元素之和等於m，能則輸出YES，不能則輸出NO。

分析：

分為取a[n]和不取a[n]的情況，則遞推公式為：

f(n,m)=f(n-1,m-a[n])||f(n-1,m) 

這裡可以用一個全局變數來輸出結果，只有有一種情況滿足了，就滿足了。

這個題目沒完，後面要補。