最近呢也是有很久没有更新博客了，主要是因为平时比较忙，毕竟等疫情彻底解封qj我也要小升初考试了，所以打算赶在今天更新点干货。
在各大oi赛事上，递归和递推算是个基础而重要的算法，递归在熟练运用后可以实现dfs，dfs是深度优先搜索，以后会讲到关于dfs的；而递推是一种用若干步可重复运算来描述复杂问题的方法，比如斐波那契数列，上楼梯等都是可以通过递推来进行实现的，而下一讲即将会具体讲述递推，今天的主题是递归
现在切入正题
一.递归
递归函数其实在比赛中特别常见，很多人在比赛的时候遇到不会的题就直接打暴力，但是如果你会递归的话，你可以用一通pmn或者dfs直接爆搜（据有关人士称，去年提高组如果pmn可以的200+。。。）那到底什么是递归呢？递归函数，即是自己调用自己，理解递归最好是通过一个例子来理解，比如，超经典的基础题，1+2+3+4+...+n-2+n-1+n=？遇到这个题，一般做法是利用for循环一个一个的累加，提供一个c++代码
#include<bits/stdc++.h>//万能头文件，建议比赛时使用 using namespace std; int s,i,n; int main() { S=0;
cin>>n; for(i=1;i<=n;i++) s=s+i; cout<<s; return 0; }
这是最简单也最直观的代码，如果使用递归实现虽然会看起来麻烦一点，但对递归的理解有好处。算法的流程图大概是是这样的
过程有点类似于倒着的for法，结合代码我们一起看看，运行结果是一样的～
#include <iostream> using namespace std; int dg(int n) //递归函数，n定义的是局部变量不冲突 { if(n==1) return 1; return (dg(n-1)+n);//进行递归 } int main() { int n; cin>>n; cout<<dg(n); return 0; }
大概就是这样子的，递归的一个基本的主体框架有两个部分，一个是反复递归的过程，还有就是中止条件，不然你的程序停不下来可很悲催的一件事，相信我，程序死活不输出你也找不到问题所在，只能浏览程序了，到了后期，这些细节要越发的注意，因为现在我写代码都动不动65+行，比如高精度就要占你数十行；
#include <iostream> using namespace std; int dg(int n) //递归函数，n定义的是局部变量不冲突 { if(终止条件) return 中止的返回值; dg(n-1);//进行递归 (举例) //递归的形式需要根据需要而调整，比如有时候你也许会是是dg(n+1)+n; } int main() { dg(n); //调用递归函数 return 0; }
递归的基本模板👆；
重点是自己调用自己这一块比较难理解，可以自己试图去尝试写一些递归程序
这里再和大家分享一道经典的题：
设有n个数已经按从大到小的顺序排列，现在输入x，判断它是否在这n个数中，如果存在则输出yes，否则输出 no；
拿到题目先分析（这里节省点位置，流程图留给你们自己去画吧🙂），这是一道比较简单的数据查找的问题，一般使用顺序查找，使用for循环，这个for循环也可以“递归化”；分别展示一下for做法和递归做法（其实还有一个做法会在未来讲二分查找的时候讲）
#include <bits/stdc++.h>//万能头可以省好多事 using namespace std; int main(){ int a[10];//用于录入10个数 int n; for(int i=0;i<10;i++) cin>>a[i]; sort(a,a+10); //快速排序函数库，加了万能头就不用加它的头文件了 cin>>n; for(int i;i<10;i++) { if(a[i]=n) { cout<<"yes"; return 0; } } cout<<"no"; return 0; }
#include <bits/stdc++.h>//万能头可以省好多事 using namespace std; int a[10];//用于录入10个数 bool b=false; void fun(int n,int k) { if(n==a[k]) { b=true; return; }//找到了，标记一下，直接跳出，不需要再找了 else if(k<0) return; //全部找完都没找到，也不用找了 fun(n,k-1);//调用部分 } int main(){ int n; for(int i=0;i<10;i++) cin>>a[i]; sort(a,a+10); //快速排序函数库，加了万能头就不用加它的头文件了 cin>>n; int k=9;//下标从0开始 fun(n,k); if(b) cout<<"yes"; else cout<<"no"; return 0; }
注释 上：for遍历法 递归遍历法 敬请期待二分查找（还不快关注。。。）
上面的做法都是可行的，运行结果一切正常
。
博客留题！：
洛谷递归题单 https://www.luogu.com.cn/training/109#problems
酌量练习，把握分度，不然会沉迷于洛谷这个花花绿绿的游戏网站 （划去）
今天的内容就是这些了，下次会讲递推，还会分享一些资料，假如你有兴趣，先点赞👍，关注➕走一波，关注后欢迎白嫖😀；
原文链接: https://www.cnblogs.com/qj-Network-Box/p/12729230.html
欢迎关注
微信关注下方公众号，第一时间获取干货硬货；公众号内回复【pdf】免费获取数百本计算机经典书籍;
也有高质量的技术群，里面有嵌入式、搜广推等BAT大佬
原创文章受到原创版权保护。转载请注明出处：https://www.ccppcoding.com/archives/342957
非原创文章文中已经注明原地址，如有侵权，联系删除
关注公众号【高性能架构探索】，第一时间获取最新文章
转载文章受原作者版权保护。转载请注明原作者出处！
