C++语言算法教程—

引子

我们经常遇到 “递归” 这个名词，却不知道是什么意思，今天我们就讲一下递归

什么是递归

看这是递龟：

好了，我们讲完了Y(^o^)Y

哈哈😄开个玩笑，我么我们来讲一个故事，听懂了，递归就懂了：

从前有个小社区
区里有个zzxjason
他给大家讲了一个故事：

从前有个小社区
区里有个zzxjason
他给大家讲了一个故事…

这个故事有什么特点？
是不是在故事中再次提到相同的故事！这就是递归的重要概念。
回到 C++，一个函数是可以调用另一个函数的Σ(⊙▽⊙"a，可如果函数调用自己？就是特例，就像故事中故事调用自己

我们把函数调用自己的现象叫递归！！
再次

举个栗子

当我们用递归写一个上面的故事：

void故事(){printf("从前有个小社区 区里有个zzxjason 他给大家讲了一个故事：");故事();}

这样，每次输出就是这个故事，故事中提到的故事就是这个故事，当然，这不是标准的 C++ 语言：

#include<bits/stdc++.h>usingnamespacestd;voidgu_shi(){printf("从前有个小社区 区里有个zzxjason 他给大家讲了一个故事：\n");gu_shi();}intmain(){gu_shi();}

当你与运行后，会发现会无限循环，这就是因为没有终止条件，函数会一直调用自己
终止条件是什么，就是当函数调用自己时，当符合条件，就不调用自己了
我们给代码加上终止条件：

#include<bits/stdc++.h>usingnamespacestd;voidgu_shi(intx){if(x==10+1){//当讲了 10 次故事时，结束（领略一下为啥是 10 + 1）return;// return前可以加东西，可return不要忘加，否则程序会继续运行下去}printf("从前有个小社区 区里有个zzxjason 他给大家讲了一个故事：\n");gu_shi(x+1);// 下一次}intmain(){gu_shi(1);// 1 代表讲了第一次故事}

执行结果：

从前有个小社区区里有个zzxjason 他给大家讲了一个故事：
从前有个小社区区里有个zzxjason 他给大家讲了一个故事：
从前有个小社区区里有个zzxjason 他给大家讲了一个故事：
从前有个小社区区里有个zzxjason 他给大家讲了一个故事：
从前有个小社区区里有个zzxjason 他给大家讲了一个故事：
从前有个小社区区里有个zzxjason 他给大家讲了一个故事：
从前有个小社区区里有个zzxjason 他给大家讲了一个故事：
从前有个小社区区里有个zzxjason 他给大家讲了一个故事：
从前有个小社区区里有个zzxjason 他给大家讲了一个故事：
从前有个小社区区里有个zzxjason 他给大家讲了一个故事：

接下来，上题\(^o^)/YES!

例题

洛谷 B2064 斐波那契数列
或
信息学奥赛一本通 1159：斐波那契数列
—（个人建议写洛谷的那题更有难度，只讲洛谷的那题）
我们看这一题：

B2064 斐波那契数列

题目描述x 时间限制 1.00s 内存限制 128.00MB
斐波那契数列是指这样的数列：数列的第一个和第二个数都为 1，接下来每个数都等于前面 2 个数之和。
给出一个正整数 a，要求斐波那契数列中第 a 个数是多少。

输入格式
第 1 行是测试数据的组数 n，后面跟着 n 行输入。每组测试数据占 1 行，包括一个正整数 a（1≤a≤30）。

输出格式
输出有 n 行，每行输出对应一个输入。输出应是一个正整数，为斐波那契数列中第 a 个数的大小。

输入输出样例

输入
4
5
2
19
1

输出
5
1
4181
1

看到这题，我们要用递归做那么我们框架先写好，就不多加讲解了：

#include<bits/stdc++.h>usingnamespacestd;intn;intfei_bo(intx){if(){}}intmain(){scanf("%d",&n);for(inti=1;i<=n;i++){inta;scanf("%d",&a);printf("%d\n",fei_bo(a));}}

我们接下来就要想fei_bo函数怎么写
我们知道，第1个和第2个数是1
那就可以：

#include<bits/stdc++.h>usingnamespacestd;intn;intfei_bo(intx){if(x==1||x==2){return1;}}intmain(){scanf("%d",&n);for(inti=1;i<=n;i++){inta;scanf("%d",&a);printf("%d\n",fei_bo(a));}}

当要第一位或第二位时，返回1
那要看斐波那契数列第x位是多少，就是第(x - 1)位加第(x - 2)位的数
于是就编好了，是不是很简单：

#include<bits/stdc++.h>usingnamespacestd;intn;intfei_bo(intx){if(x==1||x==2){return1;}returnfei_bo(x-1)+fei_bo(x-2);}intmain(){scanf("%d",&n);for(inti=1;i<=n;i++){inta;scanf("%d",&a);printf("%d\n",fei_bo(a));}}