递归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 
     
       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)=122     递归部分的主体部分就是递推公式中的主体部分 f(n)=f(n-1)*n23 */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 
     
       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!=037     递归主体为： 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 }

代码结果：