原创,转载请说明出处链接(https://www.acwing.com/blog/content/44441/)
从阶乘讲起
书接上回(文章最后有上回的链接),既然递归运行起来和循环很像,那么,我们从循环的拿手好戏,计算1+2+……+N的阶乘开始,洞察一下递归的秘密。
先上函数版的阶乘
#include<iostream>
using namespace std;
// 计算n的阶乘
int fact(int n){
int s=1;
for (int i=1;i<=n;i++){
s *= i;
}
return s;
}
int main(){
cout << fact(4) << endl; // 输出4的阶乘
return 0;
}
运行结果
24
递归的万能思路:打太极,将一部分活打回去
那么,用递归如何实现呢?我教大家一个万能思路!
先吹个牛哈……
这个万能思路,不仅用于阶乘,后续我还要讲斐波那契、上楼梯、汉诺塔、旋转矩阵……
这些程序,都是用这一个万能思路可以实现的。
所以,学万能思路时,请集中注意力!
所以,学万能思路时,请集中注意力!
所以,学万能思路时,请集中注意力!
万能思路就是:打太极
用一句话说,就是:你让我【干啥啥啥】我可干不了,如果你先【干了啥啥啥】给我,我用这个结果再【干个啥啥啥】就是你想要的了
上面这个“你”,指的是让我干活的函数,我把它套到阶乘上来,大家先听一下:
你让我【算n的阶乘】我可干不了,如果你先【算了n-1的阶乘】给我,我用这个结果再【乘以n】就是你想要的了
怎么样?是不是标准的打太极?
但这里打太极不能全打回去自己一点都不干,那是不行的!你只能将一部分活打回去——这里用专业术语就是减小规模。
当后面我们系统地学算法时讲到的分治算法、减治算法,其实都是用递归的思路在减小规模。
所以,递归的万能思路:打太极,将一部分活打回去
用递归实现阶乘
回到阶乘的例子,具体如何用递归实现呢?让我们想想万能思路的打太极:
你让我【算n的阶乘】我可干不了,如果你先【算了n-1的阶乘】给我,我用这个结果再【乘以n】就是你想要的了
这句话让我们理解了一件事,阶乘如何对自身要解决的问题,进行缩小规模。
它的思路是:
你让我算【4的阶乘】我可干不了,但我可以用【3的阶乘】4。接着是【3的阶乘】套娃
你让我算【3的阶乘】我可干不了,但我可以用【2的阶乘】3。接着是【2的阶乘】套娃
你让我算【2的阶乘】我可干不了,但我可以用【1的阶乘】2。接着是【1的阶乘】套娃
你让我算【1的阶乘】嘛……好吧,我没法打太极了,我来干活哪,【1的阶乘】就是1
这就是所谓的:大懒使小懒,气得小懒白瞪眼!
【1的阶乘】就是那个小懒,它只能干活,返回1
所以,fact(n)的函数要分两段,即:
第1段:n==1时,fact(1)的结果为1
第2段:其他时候,fact(n)的结果为fact(n-1)n
这里的n必须是自然数
到这里就可以写代码了
#include<iostream>
using namespace std;
// 计算n的阶乘
int fact(int n){
if (n==1) return 1; // 第1段:n==1时,fact(1)的结果为1
return fact(n-1)*n; // 第2段:其他时候,fact(n)的结果为fact(n-1)*n
}
int main(){
cout << fact(4) << endl; // 输出4的阶乘
return 0;
}
后续课程链接
最好的递归入门课1:https://www.acwing.com/blog/content/44441/
最好的递归入门课2:https://www.acwing.com/blog/content/44517/
后续待完善……