递归深入理解
笔来自网络记
本篇文章中，让我们深入递归，通过简单地故事，简单地示例以及详细的讲解，一起来了解，如何从普通的函数调用，一步一步转向递归？
1 说在前面的话
前面两节课，我们学习了函数的重要知识，了解了函数的重要概念！在学习今天的新知识之前，我们先复习一下前面讲解的内容。
1 温故知新
1、函数的组成
一个函数，至少需要如下几个部分：
函数类型
函数名
函数体
除此之外，大多数函数还要有函数参数。
2、为何要定义函数
主要出自两方面的考虑：
将多次使用的功能块封装起来，在使用过程中直接调用函数，无需将代码块重写，更加方便简洁。
将不同功能的代码块封装，在其他函数中调用，比全部都写在主函数里结构更加清晰。
3、函数的定义位置
一般来说，函数要定义在函数的调用之前！如果想把详细的定义过程写在后面，需要先在调用之前声明。
这种将声明和定义分开的方式，在信息学中用的比较少，但是在工程项目中，基本上都是分开的。一方面是考虑规范性，一方面是考虑代码的安全性。
4、局部变量与全局变量
局部变量和全局变量在如下几个方面不同：
作用域不同：局部变量的作用域是所在函数中，全局变量的作用域是整个程序；
初始值不同：局部变量的初值为随机值，全局变量的初值为0；
生命周期不同：局部变量的生命周期是所有函数的周期，全局变量的生命周期是整个程序的周期。
5、参数拓展
关于参数我们学习了如下方面的内容：
形参与实参：在函数声明与定义过程中的参数是形参，在函数的具体调用过程中是实参。
函数参数的引用调用：使用符号&，引用调用会改变实参本身的值。
2 老和尚讲故事
“从前有座山，山上有座庙，庙里有个老和尚，老和尚正在讲故事，讲的是：从前有座山，山上有座庙，庙里有个老和尚，老和尚正在讲故事，讲的是：从前有座山，山上有座庙，庙里有个老和尚，老和尚正在讲故事，讲的是：……”。
1 循环？
有人说，这个是循环结构，我只要不断地输出：
#include<iostream>
using namespace std;
void story(){
cout<<"从前有座山，山上有座庙，庙里有个老和尚，老和尚正在讲故事，讲的是";
}
int main() {
for(int i=0;i<100;i++){
story();
}
return 0;
}
执行结果如下：
图片
2 递归！
如果用普通方法，我们称之为循环，也没有错！
但是如果是对于我们函数来说，我们称之为递归！
那什么是递归呢？让我们接着往后看吧！
3 递归
前面我们提到递归，这里，我们来一起了解一下递归吧！
1 函数之间的调用
我们定义函数，一般都要在主函数中进行调用，如果我们定义两个函数，一个函数可以调用另外一个函数吗？可以的！比如下面的例子：
#include<iostream>
using namespace std;
void a(){
cout<<'a'<<endl;
}
void b(){
a();
cout<<'b'<<endl;
}
int main() {
b();
return 0;
}
我们要注意，要调用一个函数，在调用之前就要先把这个函数声明好。所以下面这种写法是不规范的：
如果我们有三个函数：
#include<iostream>
using namespace std;
void a(){
cout<<'a'<<endl;
}
void b(){
a();
cout<<'b'<<endl;
}
void c(){
b();
cout<<'c'<<endl;
}
int main() {
c();
return 0;
}
我们在执行c函数的时候，调用b函数，然后执行b函数的时候，调用a函数，当a函数执行完了，就要接着执行b函数剩下的，当b函数执行完，就要接着执行c函数剩下的。
如果我们有多个函数不断这样调用，我们就一层一层的调用进去，每一层执行完，就会回到上一层继续执行，直到返回到最外层执行完毕。
现在再考虑一个问题，函数能不能调用自己呢？当然是可以哒！
我们把上面的代码使用自己调用自己的话，就只需要写一个函数就可以：
#include<iostream>
using namespace std;
void c(){
cout<<'c'<<endl;
c();
}
int main() {
c();
return 0;
}
对于前面的小故事，我们可以这么写：
#include<iostream>
using namespace std;
int n = 100;
int story(){
if(n--){
cout<<"从前有座山，山上有座庙，庙里有个老和尚，老和尚正在讲故事，讲的是";
return story();
}
else return 0;
}
int main() {
story();
return 0;
}
我们再举个简单的例子，来分析一下：
#include<iostream>
using namespace std;
int output(int a){
if(a>0){
cout<<a<<endl;
return output(--a);
}
else return 0;
}
int main() {
output(5);
return 0;
}
我们对于自己定义的output函数：
int output(int a){
if(a>0){
cout<<a<<endl;
return output(--a);
}
else return 0;
}
我们在output函数里面调用了函数output，先不考虑函数名相同的问题，我们前面说，调用函数之前，我们要先定义该函数。所以，我们这个 函数之前，要先定义一个output函数：
int output(int a){ //a = 4
if(a>0){
cout<<a<<endl;
return output(--a);
}
else return 0;
}
int output(int a){ //a = 5
if(a>0){
cout<<a<<endl;
return output(--a); //--a = 4
}
else return 0;
}
而对于上面的output函数，也调用了output函数，所以我们也需要再定义一个output函数。以此推下去：
int output(int a){ //a = 0 ，返回0，结束
if(a>0){
cout<<a<<endl;
return output(--a);
}
else return 0;
}
int output(int a){ //a = 1
if(a>0){
cout<<a<<endl;
return output(--a); //--a = 0
}
else return 0;
}
int output(int a){ //a = 2
if(a>0){
cout<<a<<endl;
return output(--a); //--a = 1
}
else return 0;
}
int output(int a){ //a = 3
if(a>0){
cout<<a<<endl;
return output(--a); //--a = 2
}
else return 0;
}
int output(int a){ //a = 4
if(a>0){
cout<<a<<endl;
return output(--a); //--a = 3
}
else return 0;
}
int output(int a){ //a = 5
if(a>0){
cout<<a<<endl;
return output(--a); //--a = 4
}
else return 0;
}
但是我们注意到，这六个函数都是一样的，我们只需要写一个就可以了，但是对于程序来说，他是按照上面的这个程序一直去执行的。
2 递归
递归就是函数自己调用自己！
对于上面的代码，我们可以画一个流程图来表示：
图片
递归有去有回，其实是我们调用函数，就走进函数内部，我们称之为外层函数和内层函数。
执行外层函数的时候，我们调用了内层函数，想继续往下执行，就先要将内层函数执行完毕。而内层函数还有内层函数，我们就需要将更内层的函数执行完……执行完最内层函数，就可以执行它的外层函数，然后执行完毕执行再外层函数，一直到最外层函数，递归结束。
递归的难点在于，递归是自己调用自己，调用的层次比较深之后，很容易出错，所以我们一般在阅读程序的过程中，一般使用注释辅助我们阅读程序：
/* 使用注释，一层一层写进去分析：
output(5)
if 成立：
cout<<5<<endl;
output(4);
if 成立：
cout<<4<<endl;
output(3);
if 成立：
cout<<3<<endl;
output(2);
if 成立：
cout<<2<<endl;
output(1);
if 成立：
cout<<1<<endl;
output(0);
if 不成立
else return 1；
else
else
else
else
else
*/
3 递归案例分析
接下来，让我们通过更多的案例来理解递归吧！
1 顺序输出1-100
题目
使用递归的方式，将1-100输出；
分析
我们尝试从1开始输出，但我们进入函数是从100进入的，所以我们要先不断递去，在归来的时候，再输出。假设我们的输出函数为
show(int num);
那我们在show的后面，添加输出。（如果是逆序输出，就要先输出，后递归。）
图片
也就是如下流程：
我想输出n，我得先把n-1输出；
我想输出n-1，我得先把n-2输出；
…
我想输出3，我得先把2输出；
我想输出2，我得先把1输出；
我想输出1，我得先把0输出；
0不满足条件，返回。
1输出；
1输出结束，2输出；
2输出结束，3输出；
…
n-1输出结束，n输出。
代码
根据上面的分析，写代码如下：
#include<iostream>
using namespace std;
int output(int a){
if(a>0){
output(a-1);
cout<<a<<endl;
}
else return 0;
}
int main() {
output(100);
return 0;
}
2 递归求阶乘
题目
编写一个递归程序，求解n的阶乘，即计算:
n! = n*(n-1)*……*2*1 = n*(n-1)!
其中1! = 1
分析
跟前面一样，只不过我们要把计算的内容换一下，前面是输出，我们这里是将数据乘到一个最终的结果上面去。以5为例流程如下：
我想计算5!，我得先把4!计算出来；
我想计算4!，我得先把3!计算出来；
我想计算3!，我得先把2!计算出来；
我想计算2!，我得先把1!计算出来；
1! = 1，返回；
1!计算完毕，2!是2*1!；
2!计算完毕，3!是3*2!；
3!计算完毕，4!是4*3!；
4!计算完毕，5!是5*4!；
代码
#include<iostream>
using namespace std;
int fac(int n){
if(n>1) return n*fac(n-1);
else return 1;
}
int main() {
cout<<fac(5)<<endl;
return 0;
}
4 深入理解递归
通过上面的内容，我想大家对递归有一定的了解了，现在让我们来更加深入的理解一下递归吧！
1 递归的理解
递归有两个流程，一个是递去，一个是归来。在递去跟归来之间有一个很重要的就是分界点，也就是递去的结束条件。
也就是说递归有三要素：
递
递的结束条件
归
如果没有递的结束条件，程序就陷入死循环。就如同走进一个循环隧道，永远找不到出口。
我们可以用词典去理解递归，我们想要了解一个汉字的含义，就要查汉字的释义，那我们想要了解释义，就要再去查释义中各个汉字的意思。直到查到我们了解的字或词为止，然后我们再返回来一层一层理解，直到理解我们最初的那个汉字的含义。
2 递归与循环
递归其实是另一种形式上的循环，但比循环结构更难理解。
不同点在于：
递归是指函数的反复调用，而普通的循环，只是循环体中代码的重复调用。
在我们自己写代码的过程中，除了一些必要算法是通过递归实现的外，其他的我们尽量使用循环，避免使用递归。这是因为递归存在容易栈溢出、逻辑混乱等问题。
5 习题
我们今天给大家出两道题目：
1 递归求前n项和
使用递归的方式，求1到n的和。
2 递归求斐波那契数列
编写一个递归程序，求斐波那契数列第n项的值。
网友评论