今天我们来介绍一下递归
什么叫递归呢，其实说白了就是函数自己调用自己。如果还是不明白的小伙伴可以看看百度是怎么介绍的 =>> What is recursion
我第一次认识到递归是因为斐波那契数列。大致是这样的，有这么一个函数$F(n)$，当$n=1$或者$n=2$时$F(n)=1$,当$n>2$时，$F(n)=F(n-1)+F(n-2)$。也就是$n>2$时后面的每一项都等于前两项之和。
用代码来求第n项的话，可以这么写
#include <iostream>
using namespace std;
int n;
int F(int a)
{
if(a == 0) return 0;
else if(a == 1 || a == 2) return 1;
else return F(a - 1) + F(a - 2);
}
int main()
{
cin >> n;
cout << F(n) << endl;
return 0;
}
以上就是这简单的递归算法了。
这个代码并不难理解。
1.#include<iostream>这一头文件是C++新加的流输入输出，不懂的话也没关系，看作是scanf("%d" , &n);就行;
2.using namespace std;也不难理解，C++将标准库中的标识符都放进了std这一命名空间中，为的是保证在同一命名空间中、相同作用域中任何名字都具有唯一性，即不重名。eg：上述代码中引用了iostream这一个头文件里的cin函数，用于输入数据；如果不加上这句话，这时候编译器会提示你cin未定义（error: 'cin' was not declared in this scope），相当于你没有引用头文件吧，emmm~~~（应该是这么理解的，大佬不要捶我）。了解过的同学可能会说直接使用命名空间是不太好的，因为你写的这个代码同样可能被其他代码当作头文件引用，会造成命名重复，应该使用什么就加上什么（std::cin）,但是这只是在做项目的时候才会有这种隐患，做题的时候有且只有一个cpp文件，而且你也不想每用一个就加上std吧2333
3.剩下的就是F这个函数了，递归其实挺好理解的，首先递归必须要有边界条件，否则将会无限递归下去直到栈满。那么你将收到oj（onlinejudge）的Memory Limit Exceeded，意思就是内存满了。这个边界就是当$n=1$或者$n=2$时函数返回1（其实也可以不用n=2,不过这样减到2时会多算一次），等于0就不用说了，直接告诉main函数调用F函数结束。
让我们来模拟一下这个递归，当我们输入的是4的时候，这时候$a_1=4$,并不满足前面的条件，所以直接跳进else。但是要算$F(4)$的话得先算出$F(3) + F(2)$的值，这时候会再次调用F函数，（因为代码是从上而下执行的，所以代码暂时在这里停住了）调用后$a_2$为3,要算$F(3)$就要先算$F(2) + F(1)$,这时候又一次调用了F函数，但这一次不同了因为$a_3=2$满足$a=2$这一条件，所以函数直接返回1，然后程序跳转到$a_2$这一层调用中，$F(3) = 1 + F(1)$,然后继续调用F函数，同样$a_4=1$满足条件，函数返回1。接着又跳转回$a_2$这一层调用，$F(3) = 1 + 1$,算完$F(3)$后继续算$F(2)$,同样直接返回1，这样$F(3) + F(2)$就算完了，函数直接把结果返回给调用者，也就是main函数。在mian函数中输出$F(4)$的结果为3。至此递归就结束了。虽然理解起来挺复杂，但是认真地去模拟一下其实也没有想象的那么难（你以为就这？，不不不，还有更麻烦的递归，这只是最简单的一种）。
递归其实就相当于套娃一样一层一层地往下套，但是它返回结果的时候并不是从最上层开始的，而是从等于边界条件那一层开始逐级往上返回结果。有时候可以利用这一性质逆序输出数据2333。当然也不是递归就得返回数据，视情况而定（快速排序和归并排序的递归算法就不需要返回数据，直接修改数组的值就行了）
但是类似这种递归其实当输入的数字大起来的时候是会重复计算的，所以可以适当优化一下，具体的自行百度~~~
题解
下面给出一些常见的递归题目，也是非常简单的（因为列出数据就可以发现其实就是斐波那契数列。。。）。
1.问题描述：有一对兔子，从出生后第3个月起每个月都生一对兔子，小兔子长到第三个月后每个月又生一对兔子，假如兔子都不死，问每个月的兔子总数为多少对？
这题通过列出的数据可以发现第一个月只有1对，第二个月也只有1对，第三个月有两对，第四个月有3对，第五个月有5对。。。
所以我们直接用斐波那契数列的代码就行了
#include <iostream>
using namespace std;
int n;
int F(int a)
{
if(a == 0) return 0;
else if(a == 1 || a == 2) return 1;
else return F(a - 1) + F(a - 2);
}
int main()
{
cin >> n;
cout << F(n) << endl;
return 0;
}
2.有一楼梯共M级，刚开始时你在第一级，若每次只能跨上一级或二级，要走上第M级，共有多少种走法？（这题稍微有点不一样）
输入格式
输入数据首先包含一个整数N，表示测试实例的个数，然后是N行数据，每行包含一个整数M（1<=M<=40）,表示楼梯的级数。
输出格式
对于每个测试实例，请输出不同走法的数量
输入样例
2
2
3
输出样例
1
2
这个列出数据也可以发现，第一级的时候为0，第二级的时候为1，第三级的时候为2，第四级的时候为3。。。
所以对于0、1和2我们得处理一下。但是这里已经不可以用递归了，我是这么认为的
从列出的数据中可以发现，$n=1$时返回0，$n=2$时返回1$n=3$时返回2
就行了，$n>3$时我们可以发现，输入的是4的话只需要加1次就可以得到结果了，5的话要加两次，以此类推，加的次数与输入的数只相差了3，那么我们把输入的数减去3赋值到一个变量中，用来表示我们要加的次数，然后将1与2用另外两个变量存起来，再定义一个变量用于存结果，以便返回。这时候我们只需要用while循环或者for循环即可做出这道题
#include<iostream>
//定义常量，类似C中的#define N 100010
//比要求的数据范围多10是为了防止后续的操作导致溢出，反正内存一般是够用的，不差这几个
const int N = 100010
int arr[N];
int n;
int F(int a)
{
int value = 0 , b = 1 , c = 2;
if(a == 1)
{
return value;
}
else if(a == 2)
{
value = 1;
return value;
}
else if(a == 3)
{
value = 2;
return value;
}
else
{
a -= 3;
while( a > 0) -- a , value = b + c , b = c , c = value;
return value;
}
}
int main()
{
scanf("%d" , &n);//cin >> n;
int i = 0 , temp;
temp = n;
//for(int i = 0; i < n; ++ i)
// cin >> a[i];
while(temp --) scanf("%d" , &arr[i]) , ++ i;
int j = 0;
//for(int j = 0; j < n; ++ j)
// cout << a[j];
while(n --) printf("%d\n",F(arr[j])) , ++ j;
return 0;
}
3.你要过河，但是没有桥，只有由一排石头堆成的石头路，你一次只能跨一个石头或者两个石头，求你到第n个石头有多少种走法。(这题也稍微有点不一样)
输入格式
正整数n
输出格式
可能性的个数
输入样例1
1
输出样例1
1
输入样例2
2
输出样例2
2
这题从列出的数据中可以发现，它其实是斐波那契数列往左边一了一位的数列。
所以我们直接上递归即可（不超时的情况下）
#include<iostream>
using namespace std;
unsigned long long f(unsigned long long a)
{
if(a == 1) return 1;
else if(a == 2) return 2;
else
return f(a - 1) + f(a - 2);
}
int main()
{
unsigned long long n;
cin >> n;
cout << f(n);
return 0;
}
到这里递归就讲得差不多啦，如果还有小伙伴不是很理解的话，可以自行百度找题目去深入理解，或者直接用IDE去调试，调试的过程你就能明白递归的过程是怎样了。当然，也可以来找我击剑，加我QQ：2241141629或者Tg：https://t.me/SolitudeAlma都可以，也可以直接在AcChat上私聊我，基本每天都会打开，看到我就会回。
那么今天的讲解就到此结束啦，See you again！！！
