原创,转载请说明出处链接(https://www.acwing.com/blog/content/44441/)
大家好,今天我来讲讲递归,这应该是给孩子讲递归最好的入门课。(先自吹自擂一下,如果你见过更好的递归入门讲法并告诉我,我会感激不尽!)
先从函数调用说起
学递归首先要学函数,如果还没学函数,请出门左转……
之前学函数的时候,Yoyo问我:“爸爸,是不是函数能解决的问题,不用函数也都能解决?”
我沉思片刻,说:“基本上是,除了递归。”
为什么要沉思片刻呢?因为我也不知道,是不是递归能解决的问题,不用递归也都能解决。
有点跑题了,看下面代码,最简单的函数调用示例:
#include<iostream>
using namespace std;
void f(int n){
cout << "f:" << n << endl;
}
int main(){
cout << "m1" << endl;
f(3);
cout << "m2" << endl;
return 0;
}
下面是运行结果,我先提醒一下大家,后面会有大量的示例,请在看运行结果前,先自己猜测一下,再和运行结果做比较。如果比较是错的,你就可以带着问题看我的讲解,好吗?
运行结果:
m1
f:3
m2
对于学过函数的同学,这个还是蛮容易的吧!
继续(next)
递归就是自己调用自己
在上面代码上加一行,就是递归了
#include<iostream>
using namespace std;
void f(int n){
cout << "f:" << n << endl;
f(n); // 新增一行代码,这个就是【递归调用】
}
int main(){
cout << "m1" << endl;
f(3);
cout << "m2" << endl;
return 0;
}
好了,这就是递归,大家学会(fei)了吗?
猜一下,运行结果是什么?
Ohhhh! Noooooooo!
这个是会运行报错的(注意,编译是正常的),运行报错的学术名称为:栈溢出-Stack Overflow
这让我想起了网站stackoverflow.com,顺便提一下,如果你是计算机系的大二学生,却还不知道这个网站,那你真的是太逊了!
这个程序,具体会报什么错呢?
如果是acwing,显示的是运行超时,它把错误信息给吃掉了
Time Limit Exceeded
如果是在linux上,会视不同的C++版本不同,显示信息也不同,类似下面这个(不翻译了)
stack smashing detected
Aborted (core dumped)
拒绝无限套娃
上面的程序栈溢出,这个递归没什么用呢!我们再修改2个地方,让程序有用:
(再次提醒,先猜一下再看运行结果)
#include<iostream>
using namespace std;
void f(int n){
if (n == 0) return; // 1、新增一行代码,【递归终止】
cout << "f:" << n << endl;
f(n-1); // 2、修改【递归调用参数减小】,传n-1
}
int main(){
cout << "m1" << endl;
f(3);
cout << "m2" << endl;
return 0;
}
(再次提醒,先猜一下再看运行结果)
(再次提醒,先猜一下再看运行结果)
(再次提醒,先猜一下再看运行结果)
m1
f:3
f:2
f:1
m2
怎么样,猜对的话,请回复【竞猜点1:猜对啦!】
猜错的话,请回复【竞猜点1:猜错啦!答案为balabala……】
能想明白为什么是这个运行结果吗?我先来猜猜你的错误答案:
//错误答案
m1
f:1
f:2
f:3
m2
做错的同学,你是不是想说:“你咋知道啊?”
Yoyo说:“我不告诉你!”
递归运行起来很像循环啊
上面的程序好像也没什么用,但它好像揭示了一个秘密: 没有用循环语句,却实现了循环
请修改main()中的f(3)中的数字,修改为5就会循环5次,修改为几就会循环几次。
此时,我再问一个问题,那——如何实现死循环呢?
给你半分钟想一下!
(time…)
(time…)
(time…)
对喽,前面栈溢出的程序,不就是死循环吗?
此时,一切证据貌似指向了一个神秘的结论:递归运行起来很像循环啊
递归和循环有什么不同呢?
我不告诉你!
我不是在吊你的胃口,你现在需要自己想一想,并且自己先尝试做一下总结。
而递归和循环到底有什么不同,我会在后面的案例里面,一点一点地揭开神秘的面纱!
后续课程链接
最好的递归入门课1:https://www.acwing.com/blog/content/44441/
最好的递归入门课2:https://www.acwing.com/blog/content/44517/
后续待完善……
待完善……
最入门的一集
后续课程链接会更新(可以先收藏),一会儿就肝出下一集,敬请关注!