递归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)
这里可以用一个全局变量来输出结果,只有有一种情况满足了,就满足了。
这个题目没完,后面要补。
原文链接: https://www.cnblogs.com/Renyi-Fan/p/6914840.html
欢迎关注
微信关注下方公众号,第一时间获取干货硬货;公众号内回复【pdf】免费获取数百本计算机经典书籍
原创文章受到原创版权保护。转载请注明出处:https://www.ccppcoding.com/archives/254482
非原创文章文中已经注明原地址,如有侵权,联系删除
关注公众号【高性能架构探索】,第一时间获取最新文章
转载文章受原作者版权保护。转载请注明原作者出处!