自学内容网 自学内容网

C语言:函数递归

什么是递归

一、定义:递归其实是⼀种解决问题的⽅法,在C语⾔中,递归就是函数⾃⼰调⽤⾃⼰。
二、递归思想:把⼀个⼤型复杂问题层层转化为⼀个与原问题相似,但规模较⼩的⼦问题来求解;直到⼦问题不能再
被拆分,递归就结束了。所以递归的思考⽅式就是把⼤事化⼩的过程。递归中的递就是递推的意思,归就是回归的意思。需要深刻理解这个思想才能真正明白递归。

三、递归的限制条件
1、递归存在限制条件,当满⾜这个限制条件的时候,递归便不再继续
2、每次递归调⽤之后越来越接近这个限制条件(有点类似循环的味道,如果没有限制条件或递归后远离限制条件将会无限递归下去,最后导致栈溢出)。
举个例子:

求n的阶乘

我们知道n的阶乘的公式:n! = n ∗ (n − 1)!
例如:5! = 54321
4! = 4321
所以:5! = 5
4!
然后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;
}

在这里插入图片描述
迭代的⽅式去实现这个代码,效率就要⾼出很多了。
欢迎留言,点赞,收藏。


原文地址:https://blog.csdn.net/2403_82759827/article/details/140471888

免责声明:本站文章内容转载自网络资源,如本站内容侵犯了原著者的合法权益,可联系本站删除。更多内容请关注自学内容网(zxcms.com)!