0基础算法基础学算法 第六弹 递归

　　最近呢也是有很久没有更新博客了，主要是因为平时比较忙，毕竟等疫情彻底解封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;
}

递归的基本模板