今天我们来介绍一下递归😤


什么叫递归呢😩,其实说白了就是函数自己调用自己😲。如果还是不明白的小伙伴可以看看百度是怎么介绍的 =>> 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; //这两个if是递归结束的条件
    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(emmm,好像不一定是这个,反正意思一样就行),意思就是内存满了。这个边界就是当$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。至此递归就结束了。虽然理解起来挺复杂,但是认真地去模拟一下其实也没有想象的那么难(你以为就这?,不不不,还有更麻烦的递归,这只是最简单的一种)。

  4. 递归其实就相当于套娃一样一层一层地往下套,但是它返回结果的时候并不是从最上层开始的,而是从等于边界条件那一层开始逐级往上返回结果。有时候可以利用这一性质逆序输出数据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我们得处理一下。但是这里已经不可以用递归了,我是这么认为的

从列出的数据中可以发现,$n=1$时返回0,$n=2$时返回1,$n=3$时返回2就行了,$n>3$时我们可以发现,输入的是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!!!🎉🎉🎉

Q.E.D.


都懂一点,不是很懂的小捞仔