目录
正文开始
一. 什么是递归
什么是递归?
递归是c语言学习中一个绕不开的话题, 那什么是递归呢? 递归其实就是一种解决问题的方法, 在c语言中, 递归就是函数自己调自己.
写一个史上最简单的C语言递归代码:
#include<stdio.h>
int main(){
printf("hehe\n");
main();//这里main函数又调用自己
return 0;
}
上述代码就是一个简单的递归程序, 只不过上面的递归只是为了演示递归的基本形式, 不是为了解决问题, 代码最终也会陷入死循环, 导致栈溢出 (Stack overflow).
二. 递归的限制条件
- 递归的思想:
把一个大模型复杂问题层层转化为一个与原问题相似, 但规模较小的问题来求解, 直到子问题不能再被拆分, 所以递归的思考方式是把大问题化小的过程.
递归中的递就是递推的意思, 归就是回归的意思, 接下来请读者来体会. - 递归的限制条件:
递归在书写的时候, 有两个必要条件:
- 递归存在限制条件, 当满足这个限制条件的时候, 递归便不再继续.
- 每次递归调用之后越来越接近这个限制条件.
在下面的举例中, 我们会逐步体会到这两个限制条件
三. 递归的举例
- 举例1: 求n的阶乘
一个正整数的阶乘(factorial)是所有小于及等于该数的正整数的积, 并且0的阶乘为1.
自然数n的阶乘写作n!
题目:计算n的阶乘(不考虑溢出), n的阶层就是1~n的数字积累相乘.
- 分析和代码实现
我们知道n的阶乘的公式: n! = n * (n-1) !
举例:
5!=5*4*3*2*1
4!=4*3*2*1
所以5!=5*4!
这样的思路就是把一个较大的问题, 转化成一个与原问题相似, 但规模较小的问题来求解的.
当n==0的时候,n的阶乘是1, 其余的n的阶乘都是可以通过公式计算.
n的阶乘的递归公式如下:
那我们就可以写出函数Fact求n的阶乘, 假设Fact(n)就是用来求n的阶乘, 那么Fact(n-1)就是求n-1的阶乘, 函数如下:
int Fact(int n){
if(n==0)
return 1;
else
return n*Fact(n - 1);
}
测试:
#include<stdio.h>
int Fact(int n) {
if (n == 0)
return 1;
else
return n * Fact(n - 1);
}
int main() {
int n = 0;
scanf("%d", &n);
int result = Fact(n);
printf("%d\n", result);
return 0;
}
运行结果:
画图推演:
- 举例2: 顺序打印一个整数的每一位
题目: 输入一个整数m, 按照顺序打印整数的每一位
比如:
输入:1234 输出:1 2 3 4
输入:520 输出:5 2 0
分析和代码
这个题目, 放在我们面前, 首先想到的是, 怎么得到这个数的每一位呢?
如果n是一位的话, n的每一位就是n自己
n如果超过1位的话, 就拆分每一位
1234%10就能得到4, 然后1234/123, 这就相当于去掉了4, 以此类推, 不断的%10和/10的操作, 直到1234的每一位都得到; 但是这里有个问题就是得到的数字顺序是倒着的. 但是我们有了灵感, 我们发现其实一个数字的最低为是最容易得到的, 通过%10就得到, 那我们假设写一个函数Print来打印n的每一位,如下所示:
Print(n)
如果n是1234,那么表示
print(1234) 打印1234的每一位
其中1234中4可以通过%10得到,那么
print(1234)就可以拆分成为两步:
1.print(1234/10)
2.printf(1234%10)
完成上述2步,那就完成了1234每一位的打印
那么print(123)又可以拆分为printf(123/10)+printf(123%10)
以此类推下去, 就有
Print(1234)
==>Print(123) +printf(4)
==>print(12) +printf(3)
==>print(1) + printf(2)
==>printf(1)
直到被打印的数字变成一位数的时候, 就不需要拆分, 递归结束
那么代码完成也就比较清楚:
#include<stdio.h>
void Print(int n) {
if (n > 10) {
Print(n / 10);
}
printf("%d ", n % 10);
}
int main() {
int m = 0;
scanf("%d", &m);
Print(m);
return 0;
}
输入输出结果:
画图推演:
四. 递归与迭代
递归是一种很好的编程技巧, 但是和很多技巧一样, 也是可能被误用的, 就像举例1一样, 看到推导的公式, 很容易写出递归的形式:
int Fact(int n){
if(n==0)
return 1;
else
return n*Fact(n - 1);
}
Fact函数是可以产生正确的结果, 但是在递归函数调用的过程中涉及一些运行时的开销.
所以如果不想使用递归就想得到其它的方法, 通常就是迭代的方式(通常就是循环的方式).
比如:计算n的阶乘,也是可以产生1~n的数字累计乘在一起的
int Fact(int n) {
int i = 0;
int ret = 1;
for (i = 0; i <= n; i++) {
ret *= i;
}
return ret;
}
事实上，我们看到的许多问题是以递归的形式进⾏解释的，这只是因为它⽐⾮递归的形式更加清晰，
但是这些问题的迭代实现往往⽐递归实现效率更⾼。
当⼀个问题⾮常复杂，难以使⽤迭代的⽅式实现时，此时递归实现的简洁性便可以补偿它所带来的运行时开销。
举例3：求第n个斐波那契数
我们也能举出更加极端的例⼦，就像计算第n个斐波那契数，是不适合使⽤递归求解的，但是斐波那契
数的问题通过是使⽤递归的形式描述的，如下：
看到这公式，很容易诱导我们将代码写成递归的形式，如下所⽰：
int Fib(int n)
{
if(n<=2)
return 1;
else
return Fib(n-1)+Fib(n-2);
}
测试代码：
#include <stdio.h>
int main()
{
int n = 0;
scanf("%d", &n);
int ret = Fib(n);
printf("%d\n", ret);
return 0;
}
当我们n输⼊为50的时候，需要很⻓时间才能算出结果，这个计算所花费的时间，是我们很难接受的，
这也说明递归的写法是⾮常低效的，那是为什么呢？
其实递归程序会不断的展开，在展开的过程中，我们很容易就能发现，在递归的过程中会有重复计
算，⽽且递归层次越深，冗余计算就会越多。我们可以作业测试:
#include <stdio.h>
int count = 0;
int Fib(int n)
{
if(n == 3)
count++;//统计第3个斐波那契数被计算的次数
if(n<=2)
return 1;
else
return Fib(n-1)+Fib(n-2);
}
int main()
{
int n = 0;
scanf("%d", &n);
int ret = Fib(n);
printf("%d\n", ret);
printf("\ncount = %d\n", count);
return 0;
}
在计算第40个斐波那契数的时候，使⽤递归⽅式，第3个斐波那契数就被重复计算了
39088169次，这些计算是⾮常冗余的。所以斐波那契数的计算，使⽤递归是⾮常不明智的，我们就得
想迭代的⽅式解决。
我们知道斐波那契数的前2个数都1，然后前2个数相加就是第3个数，那么我们从前往后，从⼩到⼤计
算就⾏了。
这样就有下⾯的代码：
int Fib(int n)
{
int a = 1;
int b = 1;
int c = 1;
while(n>2)
{
c = a+b;
a = b;
b = c;
n--;
}
return c;
}
迭代的⽅式去实现这个代码，效率就要⾼出很多了。
有时候，递归虽好，但是也会引⼊⼀些问题，所以我们⼀定不要迷恋递归，适可⽽⽌就好。