1. 递归是什么?
递归其实是⼀种解决问题的⽅法,在C语⾔中,递归就是函数⾃⼰调⽤⾃⼰。
#include
void print()
{
printf("hehe");
print();
}
int main()
{
printf("hehe");
print();
}
在上面的函数中函数实现了自己调用自己,去实现我们想要去实现的功能,这种就是函数递归,上面那个是一种死递归
函数递归的思想其实就是我们实用体会大事化,小小事化了,我们来举一个n阶乘的例子。
n!=nx(n-1)x………x1
一个正整数的阶乘是所有小于及等于该数正整数的积。
3!=3x2x1
int fact(int n)
{
if (n == 0)
return 1;
else
return n * fact( n- 1);
}
int main()
{
int n = 0;
scanf("%d", &n);
int ret = fact(n);
printf("%d", ret);
}
然后我们会发现,当我们去求一个更高位数的阶乘。其实就等于这个位数乘以它减一的阶乘。比如我去求5的阶乘。
5的阶乘=12×345。
其实5的阶乘=4!x5。
我们怎么去分析这个,很简单当我们输入5的时候。我们调用了我们所使用的函数fact
根据判断条件,5不等于1,我们的N=5。
所以我们返回Nfact(n-1):此时此刻,我们就又调用了fact(n-1)即调用函数fact(4)根据条件又不成立,我们又要调用fact(3),…fact(2),fact(1),fact(0)
知道我们调用这个函数称为理,他会给我们返回1,fact(0)返回了1
fact(服务器托管网1)=fact(0)*1=1
fact(2)=fact(1)*2=2
fact(3)=fact(2)*2=6
所以fact(4)返回了24,Fact(5)=5*24
我们得到了答案。
我们通过分析我们上面所写的代码
int fact(int n)
{
if (n == 0)
return 1;
else
return n * fact( n- 1);
}
int main()
{
int n = 0;
scanf("%d", &n);
int ret = fact(n);
printf("%d", ret);
}
我们明白递归的回归是有条件的。
我们可以利用这种想法,利用递归的思想去打印一个数的每一位。那我们如何思考?
当我们将一个数除10 就能够得到他出最后一位数之前的数,那么我们将这个数模10得到的余数。比如
1234/10=123
1234%10=4
123/10=12
123%10=3
12/10=1
12%10=2
1/10=0
1%10=1
我们利用这种想法,加上函数的递归写出了下面这样的代码。
int division(int num)
{
if (num / 10 == 0)
return num;
else
printf("%dn", num % 10);
return division(num / 10);
}
int main()
{
int num = 0;
scanf("%d", &num);
int ret = division(num);
printf("%d",ret);
}
但是打印出来的是倒序,那我们如何有序的打印?
我们转变一下思想,其实我们可以利用,C语言中的除法,取得了前面的数。我们将我们取得的前面的数一一打印出来,然后再打印最后一位数
比如1234/10=123
123/10=12 12/10=1
然后利用if打印最后一位。
就这样我们就打印了前的数,然后再利用我模去打印最后一位数。我们就可以写出下面这样的代码
int division(int num)
{
if (num>9)
{
division(num/10);
}
printf("%d ", num % 10);
}
int main()
{
int num = 0;
scanf("%d", &num);
int ret = division(num);
printf("%d", ret);
}
我们了解过开始的死递归,那么每一次调用都会申请空间吗?
每一次函数调用,都会向内存栈区上申请一块空间
这一块空间主要是用来存放函数的中局部变量,和函数调用过程中的上下文的信息这个一块空间一般叫:函数的运行时堆栈,也叫函数栈帧空间。
编译会自动根据需要开辟空间的!
栈帧我后面会讲的,Fact函数是可以产生正确的结果,但是在递归函数调用的过程中涉及一些运行时的开销。
在C语言中每一次函数调用,都要需要为本次函数调用在栈区申请一块内存空间来保存函数调用期间的各种局部变量的值,这块空间被称为运行时堆栈,或者函数线帧。
函数不返回,函数对应的栈帧空间就一直占用,所以如果函数调用中存在递归调用的话,每一次递归函数调用都会开辟属于自己的栈帧空间,直到函数递归不再继续,开始回归,才逐层释放栈帧空间。
所以如果采用函数递归的方式完成代码,递归层次太深,就会浪费太多的栈帧空间,也可能引起栈溢出
所以如果不想使用递归就得想其他的办法,通常就是迭代的方式,通常就是循环的方式)
利用循环去取得n的阶乘
int main()
{
int n = 0;
scanf("%d", &n);
int i = 0;
int ret = 1;
for (i = 1; i
当我们去求第n个菲波那契数列,我们就会写出像下面这样的代码。
int series(int n)
{
if (n == 1 || n == 2)
return 1;
else
{
return series(n - 1) + series(n - 2);
}
}
int main()
{
int n = 0;
scanf("%d",&n);
int ret = series(n);
printf("%d", ret);
}
当我们去求第50个斐波那契数,计算就会很慢,那么我们就可以利用愉快的方式去解决这个问题比如循环
nt main()
{
int a = 1;
int b = 1;
int num = 0;
scanf("%d", &num);
int ret = 0;
while (num>=3)
{
ret = a + b;
a =服务器托管网 b;
b = ret;
num--;
}
printf("%d", ret);
return 0;
}
等我们完全了解上面两种方法的时候,那我们在什么时候去使用的,当我们使用递归可以运行没有过大的缺陷的时候,就可以使用递归
在这里我分享两个问题。
汉诺塔问题
青蛙跳台阶问题
如果想了解我后面会发表文章
服务器托管,北京服务器托管,服务器租用 http://www.fwqtg.net
机房租用,北京机房租用,IDC机房托管, http://www.fwqtg.net
它是一个基于chrome V8引擎的js运行环境 1.fs模块 fs.readfile:读文件只能创建文件不能创建路径 fs.writefile:写文件 write写文件会被覆盖 需要先导入 const fs=require(‘fs’) 2.path路径模块 …