今天我们来介绍一下递归😤
什么叫递归呢😩，其实说白了就是函数自己调用自己😲。如果还是不明白的小伙伴可以看看百度是怎么介绍的 =>> What is recursion
我第一次认识到递归是因为斐波那契数列。大致是这样的，有这么一个函数，当或者时,当时，。也就是时后面的每一项都等于前两项之和。
用代码来求第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; //这两个if是递归结束的条件
else return F(a - 1) + F(a - 2);
}
int main()
{
cin >> n;
cout << F(n) << endl;
return 0;
}
以上就是这简单的递归算法了。
这个代码并不难理解😏。
-
#include<iostream>这一头文件是C++新加的流输入输出，不懂的话也没关系，看作是scanf("%d" , &n);就行; -
using namespace std;也不难理解，C++将标准库中的标识符都放进了std这一命名空间中，为的是保证在同一命名空间中、相同作用域中任何名字都具有唯一性，即不重名。eg：上述代码中引用了iostream这一头文件里的cin函数，用于输入数据；如果不加上这句话，这时候编译器会提示你cin未定义（error: cin was not declared in this scope），相当于你没有引用头文件吧，emmm~~~（应该是这么理解的，大佬不要捶我）。了解过的同学可能会说直接使用命名空间是不太好的，因为你写的这个代码同样可能被其他代码当作头文件引用，会造成命名重复，应该使用什么就加上什么（std::cin）,但是这只是在做项目的时候才会有这种隐患，做题的时候有且只有一个cpp文件，而且你也不想每用一个就加上std吧2333
-
剩下的就是F这个函数了，递归其实挺好理解的，首先递归必须要有边界条件，否则将会无限递归下去直到栈满。那么你将收到oj（onlinejudge）的Memory Limit Exceeded（emmm，好像不一定是这个，反正意思一样就行），意思就是内存满了。这个边界就是当或者时函数返回1（其实也可以不用n=2,不过这样减到2时会多算一次），等于0就不用说了，直接告诉main函数调用F函数结束。
让我们来模拟一下这个递归，当我们输入的是4的时候，这时候,并不满足前面的条件，所以直接跳进else。但是要算的话得先算出的值，这时候会再次调用F函数，（因为代码是从上而下执行的，所以代码暂时在这里停住了）调用后为3,要算就要先算,这时候又一次调用了F函数，但这一次不同了因为满足这一条件，所以函数直接返回1，然后程序跳转到这一层调用中，,然后继续调用F函数，同样满足条件，函数返回1。接着又跳转回这一层调用，,算完后继续算,同样直接返回1，这样就算完了，函数直接把结果返回给调用者，也就是main函数。在mian函数中输出的结果为3。至此递归就结束了。虽然理解起来挺复杂，但是认真地去模拟一下其实也没有想象的那么难（
你以为就这？，不不不，还有更麻烦的递归，这只是最简单的一种）。 -
递归其实就相当于套娃一样一层一层地往下套，但是它返回结果的时候并不是从最上层开始的，而是从等于边界条件那一层开始逐级往上返回结果。有时候可以利用这一性质逆序输出数据2333。当然也不是递归就得返回数据，视情况而定（快速排序和归并排序的递归算法就不需要返回数据，直接修改数组的值就行了，因为习惯上把数组定义为全局变量，所以不需要数组当作参数传入或者是返回值返回）
但是类似这种递归其实当输入的数字大起来的时候是会重复计算的，所以可以适当优化一下，具体的自行百度~~~
题解🙆♂
下面给出一些常见的递归题目，也是非常简单的（因为列出数据就可以发现其实就是斐波那契数列。。。）。
1.问题描述：有一对兔子，从出生后第3个月起每个月都生一对兔子，小兔子长到第三个月后每个月又生一对兔子，假如兔子都不死，问每个月的兔子总数为多少对？
这题通过列出的数据可以发现第一个月只有1对，第二个月也只有1对，第三个月有2对，第四个月有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我们得处理一下。但是这里已经不可以用递归了，我是这么认为的从列出的数据中可以发现，时返回0，时返回1，时返回2就行了，时我们可以发现，输入的是4的话只需要加1次就可以得到结果了，5的话要加2次，以此类推，加的次数与输入的数只相差了3，那么我们把输入的数减去3赋值到一个变量中，用来表示我们要加的次数，然后将1与2用另外两个变量存起来，再定义一个变量用于存结果，以便返回。这时候我们只需要用while循环或者for循环即可做出这道题🤣🤣🤣
（其实这种两个变量的做法也可以顶替递归做斐波那契数列的题，思路是一样的）
#include<cstdio>
//定义常量，类似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去调试，调试的过程你就能明白递归的过程是怎样了。当然，还是不懂的话可以来找我击剑哦~~~🤺🤺🤺
那么今天的讲解就到此结束啦，See you again！！！🎉🎉🎉
Alipay 
Wechat