文章目录
什么是递归
一、定义:递归其实是⼀种解决问题的⽅法,在C语⾔中,递归就是函数⾃⼰调⽤⾃⼰。
二、递归思想:把⼀个⼤型复杂问题层层转化为⼀个与原问题相似,但规模较⼩的⼦问题来求解;直到⼦问题不能再
被拆分,递归就结束了。所以递归的思考⽅式就是把⼤事化⼩的过程。递归中的递就是递推的意思,归就是回归的意思。需要深刻理解这个思想才能真正明白递归。
三、递归的限制条件
1、递归存在限制条件,当满⾜这个限制条件的时候,递归便不再继续
2、每次递归调⽤之后越来越接近这个限制条件(有点类似循环的味道,如果没有限制条件或递归后远离限制条件将会无限递归下去,最后导致栈溢出)。
举个例子:
求n的阶乘
我们知道n的阶乘的公式:n! = n ∗ (n − 1)!
例如:5! = 54321
4! = 4321
所以:5! = 54!
然后4!=4*3!
直到不能再分为止。
这就是递归,把⼀个较⼤的问题,转换为⼀个与原问题相似,但规模较⼩的问题来求解的。
思路就是把n分到0,然后将n==0的值返回到上一个调用它函数中去。
代码实现
#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 ret = Fact(n);
printf("%d\n", ret);
return 0;
}
推演运行过程
顺序打印⼀个整数的每⼀位
#include <stdio.h>
void print(int n)
{
if(n>9)
{
print(n/10);
}
printf("%d ",n%10);
}
int main()
{
int n=0;
scanf("%d",&n);
print(n);
return 0;
}
把Print(1234)打印1234每⼀位,拆解为⾸先Print(123)打印123的每⼀位,再打印得到的4把Print(123)打印123每⼀位,拆解为⾸先Print(12)打印12的每⼀位,再打印得到的3直到Print打印的是⼀位数,直接打印就⾏。
递归与迭代
由于递归程序会不断的展开,在展开的过程中,我们很容易就能发现,在递归的过程中会有重复计算,⽽且递归层次越深,冗余计算就会越多,会大大降低效率。
例如这个求斐波那契数如果不断向下递归展开,像Fib(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;
}
迭代的⽅式去实现这个代码,效率就要⾼出很多了。
欢迎留言,点赞,收藏。