【C语言】函数的系统化精讲(三)2

简介: 【C语言】函数的系统化精讲(三)

【C语言】函数的系统化精讲(三)1:https://developer.aliyun.com/article/1474657

3.1递归的思考

递归是一种有用的编程技巧,但像其他技巧一样,也容易被误用。举例来说,看到推导的公式,很容易就被写成递归的形式犹如数学函数一样。

int Fact(int n)
{
  if(n<=0)
  return 1;
  else
  return n*Fact(n-1);
}
• 1
• 2
• 3
• 4
• 5
• 6
• 7

Fact函数是可以产⽣正确的结果,但是在递归函数调⽤的过程中涉及⼀些运⾏时的开销。

什么是运行时的开销呢?

在C语言中,每次函数调用都需要在栈区为本次函数调用申请一块内存空间,用来保存函数调用期间的各种局部变量的值。这块空间被称为运行时堆栈,或者函数栈帧。如果函数没有返回,对应的栈帧空间就会一直被占用。因此,如果函数调用中存在递归调用,每次递归函数调用都会开辟属于自己的栈帧空间,直到函数递归不再继续,开始回归,才逐层释放栈帧空间。因此,如果采用函数递归的方式完成代码,递归层次太深就会浪费太多的栈帧空间,也可能引起栈溢出(stack overflow)的问题。


所以如果不想使用递归就得想其他的办法,通常就是迭代的方式(通常就是循环的方式)。

⽐如:计算n的阶乘,也是可以产⽣1~n的数字累计乘在⼀起的。

int Fact(int
{
  int i = 0;
  int ret = 1;
  for (i = 1; i <= n; i++)
  {
    ret *= i;
  }
  return ret;
}
int main()
{
  int n = 0;
  scanf("%d", &n);
  int ret = Fact(n);
  printf("%d\n", ret);
  return 0;
}

上述代码是能够完成任务,并且效率是⽐递归的⽅式更好的。

事实上,我们看到的许多问题是以递归的形式进⾏解释的,这只是因为它⽐⾮递归的形式更加清晰,

但是这些问题的迭代实现往往⽐递归实现效率更⾼。

当⼀个问题⾮常复杂,难以使⽤迭代的⽅式实现时,此时递归实现的简洁性便可以补偿它所带来的运⾏时开销。

3.2求第n个斐波那契数

我们还可以举出更极端的例子,比如计算第n个斐波那契数,不适合使用递归求解,但是斐波那契数的问题通常是用递归的形式描述的,如下:

看到这公式,很容易想到这还不简单啊,将代码递归的形式走起,如:

int Fib(int n)
{
  if(n<=2)
  return 1;
  else
  return Fib(n-1)+Fib(n-2);
}

当我们输入为50时,光标还在闪烁需要很长时间才能算出结果,这个计算所花费的时间,是我们很难接受的,这也说明递归的写法是非常低效的,那是为什么呢? 此时程序并没有停止,而是不断的计算,我们可以Ctrl+Shift+Esc打开任务管理器,我们可以看到我们的程序的CPU占比13.7%(这个13.7%不是最高的),(由于代码运行起来后,电脑便会风扇转起,直接CPU干起来,博主电脑无法立刻截不了图,所以导致截图不到想要的高CPU运行百分比,推荐你们也可以尝试一下)

其实递归程序会不断的展开,在展开的过程中,我们很容易就能发现,在递归的过程中会有重复计算,⽽且递归层次越深,冗余计算就会越多。

这里我们发现,在计算第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;
}

总结

递归虽好,但是也会引⼊⼀些问题,所以我们⼀定不要迷恋递归,适当就好。

递归和循环的选择:

1,如果使用递归写代码,非常容易,写出的代码没问题,那就使用递归。

2,如果递归写出的问题,是存在明显的缺陷,那就不能使用递归,得用迭代的方式处理。

相关文章
|
6天前
|
存储 C语言
C语言学习记录——动态内存函数介绍(malloc、free、calloc、realloc)
C语言学习记录——动态内存函数介绍(malloc、free、calloc、realloc)
14 1
|
3天前
|
存储 API C语言
C语言函数大全--e开头的函数
【6月更文挑战第6天】本篇介绍 C语言中 e开头的函数【C语言函数大全】
26 16
C语言函数大全--e开头的函数
|
5天前
|
存储 Linux Serverless
C语言函数大全--d开头的函数
【6月更文挑战第5天】本篇介绍 C语言中 d开头的函数【C语言函数大全】
13 1
C语言函数大全--d开头的函数
|
5天前
|
API C语言 开发者
C语言中抽象函数与具体实现的命名与组织
在C语言的嵌入式系统和开源软件开发中,良好地处理抽象函数与实现对于代码质量至关重要。建议将API作为接口定义操作,使用函数指针实现动态替换。避免使用`Impl`后缀,推荐用`Callback`或`Handler`表示具体实现。回调函数用于异步事件处理,通过指针传递。示例展示了C语言中函数指针的用法,嵌入式项目常通过目录结构区分平台相关代码。清晰的命名和组织能提升代码可读性和团队协作效率。
|
6天前
|
JavaScript Java 测试技术
基于ssm+vue.js+uniapp小程序的C语言在线评测系统附带文章和源代码部署视频讲解等
基于ssm+vue.js+uniapp小程序的C语言在线评测系统附带文章和源代码部署视频讲解等
7 0
|
6天前
|
C语言
C语言进阶——文件的读写(文件使用方式、文件的顺序读写、常用函数、fprintf、fscanf)
C语言进阶——文件的读写(文件使用方式、文件的顺序读写、常用函数、fprintf、fscanf)
5 0
|
6天前
|
C语言 C++
C语言学习记录——内存函数(memcpy、memmove、memcmp、memset、模拟实现memcpy、模拟实现memmove)
C语言学习记录——内存函数(memcpy、memmove、memcmp、memset、模拟实现memcpy、模拟实现memmove)
15 3
|
6天前
|
C语言
C语言学习记录——鹏哥字符分类函数、字符转换函数
C语言学习记录——鹏哥字符分类函数、字符转换函数
10 2
|
6天前
|
安全 编译器 C语言
C语言学习记录——字符串相关函数及部分模拟(strcmp、strncmp、strncat、strncpy、strstr、strtok、strerror)
C语言学习记录——字符串相关函数及部分模拟(strcmp、strncmp、strncat、strncpy、strstr、strtok、strerror)
11 1
|
6天前
|
C语言
C语言学习记录——模拟字符串相关函数(strcpy、strlen、strcat)相关知识-const、typedef
C语言学习记录——模拟字符串相关函数(strcpy、strlen、strcat)相关知识-const、typedef
9 1