Compiler- 尾调用

news/2024/3/29 17:54:33/文章来源:https://blog.csdn.net/weixin_43844521/article/details/130361098

我们还是用例子来引入本次要探讨的问题--尾调用

#include <stdio.h>int fib(int a)
{return a <= 2 ? 1 : fib(a - 1) + fib(a - 2);
}int main()
{int n,result;scanf("%d",&n);result = fib(n);printf("result is %d.\n",result);return 0;
}

这段代码的含义应该很清晰。那下面这一段呢?

#include <stdio.h>int repeat = 0;int fib(int a)
{int result;if (a <= 2) return 1;if ((a - 1) <= 2) {   // a <= 3 的情况result = 1;} else {result = fib(a - 2) + fib(a - 3);}if ((a - 2) <= 2) {   // a <= 4 的情况result += 1;} else {result += fib(a - 3) + fib(a - 4);}return result;
}int main()
{int n;int result;scanf("%d",&n);result = fib(n);printf("result is %d.\n",result);return 0;
}

这两个代码在功能上是一致的,只不过第二个代码把a <= 3 和 a <= 4 的情况也单独拎出来,类似于之前提到的循环展开(Compiler- 循环展开_青衫客36的博客-CSDN博客),也是为了提高效率

我们对上面的两个程序稍作修改,加上计时函数,如下所示

// fib.c
#include <stdio.h>
#include <time.h>clock_t to_duration_in_ms(clock_t start, clock_t end) 
{return 1000 * (end - start) / CLOCKS_PER_SEC;
}int repeat = 0;int fib(int a)
{repeat ++;return a <= 2 ? 1 : fib(a - 1) + fib(a - 2);
}int main()
{int n,result;clock_t start, end;scanf("%d",&n);start = clock();result = fib(n);end = clock();printf("result is %d,time is %ldms,repeat is %d.\n",result,to_duration_in_ms(start,end),repeat);return 0;
}
// fib1.c
#include <stdio.h>
#include <time.h>clock_t to_duration_in_ms(clock_t start, clock_t end) 
{return 1000 * (end - start) / CLOCKS_PER_SEC;
}int repeat = 0;int fib(int a)
{int result;repeat ++;if (a <= 2) return 1;if ((a - 1) <= 2) {result = 1;} else {result = fib(a - 2) + fib(a - 3);}if ((a - 2) <= 2) {result += 1;} else {result += fib(a - 3) + fib(a - 4);}return result;
}int main()
{int n,result;clock_t start, end;scanf("%d",&n);start = clock();result = fib(n);end = clock();printf("result is %d,time is %ldms,repeat is %d.\n",result,to_duration_in_ms(start,end),repeat);return 0;
}

然后来对比一下这两个程序的运行时间time和重复次数repeat

可以看到两个程序的运行结果是一样的,但是运行时间和重复次数明显第二个更优。

为什么会出现这样的差别呢?

我们以fib(3)为例,来看看在这两个代码中是如何执行的。

●  对于第一段代码,fib(3)->fib(2)+fib(1);fib(2)进行递归,返回1;fib(1)进行递归,返回1。

●  对于第二段代码,在两个if条件判断的第一个分支处返回。

所以,第二段代码节省了不少的函数调用的时间。而我们知道,函数调用,要分配栈,要传参总是要花费时间的。

下面我们来看看编译器优化的效果,使用GCC进行编译,选择-O3,查看运行时间。

相比于之前的386ms和328ms,经过O3优化后的132ms还是很厉害的hh~

那如果不用递归,而是用循环的方式计算斐波那契数列呢?我们来看下面代码的执行时间。

// fibc.c
#include <stdio.h>
#include <time.h>
clock_t to_duration_in_ms(clock_t start, clock_t end) 
{return 1000 * (end - start) / CLOCKS_PER_SEC;
}int repeat = 0;int fibc(int n)
{ int f1 = 1;int f2 = 1;int result;if(n == 1 || n == 2) return 1;else {for(int i = 2; i < n; i++){result = f1 + f2;f1 = f2;f2 = result;}}return result;
}int main()
{int n;int result;clock_t start, end;scanf("%d",&n);start = clock();result = fibc(n);end = clock();printf("result is %d,time is %dms,repeat is %d.\n",result,to_duration_in_ms(start,end),repeat);return 0;
}

运行时间为惊人的0ms,由此可以体会到函数调用、递归执行的效率问题。

我们在学习递归和迭代的时候,也会知道递归的代码容易看懂,而迭代展开的代码不好懂。

那有没有一种方法既是递归,并且效率又比较高呢?(本质上是降低函数调用的代价)

这种方式是尾递归,特点是,这种调用在整个函数的最后一步,它调用完之后整个函数就结束了,由于这是函数最后一步,做完之后函数调用堆栈框架也可以拆除了。注意,此种写法,斐波那契数列的加法操作是在参数传递这个过程中完成的。

因为这个调用发生在函数的最后一部分,所以在优化时,每当进行函数调用,就没必要重新分配栈了,这样就把函数调用的代价降到很低。

#include <stdio.h>
#include <time.h>
clock_t to_duration_in_ms(clock_t start, clock_t end) 
{return 1000 * (end - start) / CLOCKS_PER_SEC;
}int repeat = 0;int fibtail(int n,int ret1, int ret2)
{if(n==1) return ret1;else return fibtail(n-1,ret2, ret1+ret2);
}int main()
{int n;int result;clock_t start, end;scanf("%d",&n);start = clock();result = fibtail(n,1,1);end = clock();printf("result is %d,time is %dms,repeat is %d.\n",result,to_duration_in_ms(start,end),repeat);
}

我们看一下这个程序的运行时间

我们来分析一个简单的尾调用

#include <stdio.h>int x = 1;
int g(int z)
{return x + z;
}int f(int y)
{int x = y + 1;return g(y*x);
}int main(){printf("The result is %d.\n",f(3));return 0;
}

看一下生成的汇编代码。

以下是开启-O3优化的情况: 

可以看到,在函数f和g中,代码得到了大幅的缩减。甚至,在优化之后,两个函数都没有分配栈空间,直接进行了计算。再进一步的,函数f并没有调用函数g,而是直接把函数g的工作给做了。所以,这种优化真是很了不起的。


以上为中科大软件学院《编译工程》课后总结,感谢郭燕老师的倾心教授,老师讲的太好啦(^_^) 

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.luyixian.cn/news_show_103318.aspx

如若内容造成侵权/违法违规/事实不符,请联系dt猫网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

创建路由React router(使用react-router dom V6版本)

React路由 隔了很长一段时间&#xff0c;重新捡起来React学习。 发现React的路由从原来的 Switch改成了Routes。nice&#xff0c;nice&#xff0c;nice&#xff01;&#xff01;&#xff01;&#xff01; 刚开始接触确实还是有一点生疏的。之前的关于【传参】【js跳转】【跳转模…

矿井下无人值守变电所电力监控系统的探讨与产品选型

摘要&#xff1a;为了探讨井下无人值守变电所的电力监控系统技术&#xff0c;以西山煤电马兰矿为背景&#xff0c;详细阐述了井下无人值守变电所电力监控系统技术的各项基本参数&#xff0c;如额定工作电压及整机输入视在功率、交换机或监控分站的传输口、高压配电装置的传输口…

下载VMWare

1、首先登录到vmware官网 官网&#xff1a;https://www.vmware.com/ 2、点击Resource 3、找到Product Downloads 4、找到我们要下载的产品&#xff0c;点击download product 5、选择自己要下载的版本和对应的系统 6、点击去下载 7、点击download now

国云筑基“翼”气风发,天翼云以科技创新绘就数字中国蓝图

科技云报道原创。 全球新一轮技术革命方兴未艾&#xff0c;特别是以数字技术为核心的信息技术革命&#xff0c;正在实现群体突破和加快广泛深度应用。 从2017年的“促进数字经济加快成长”&#xff0c;到2019年的“壮大数字经济”&#xff0c;到2020年的“全面推进‘互联网&am…

SpringBoot的配置和日志

1.配置文件的作用和意义 配置文件中配置整个项目中所有重要的数据&#xff0c;比如&#xff1a; 1.数据库的连接信息&#xff08;包含用户名和密码的设置&#xff09;&#xff1b; 2.项目的启动端口&#xff1b; 3.第三方系统的调用秘钥等信息&#xff1b; 4.用于发现和定位问…

Unity之OpenXR+XR Interaction Toolkit实现 抓取物体

前言 我们今天来说一下如何使用XR Interaction Toolkit来实现和3D物体的交互之&#xff1a;抓取&#xff0c;简单说就是通过VR手柄拿起来一个物体。 二.准备工作 有了前两篇的配置介绍,我们就不在详细说明这些了&#xff0c;大家自行复习 Unity之OpenXRXR Interaction Toolk…

BPF技术学习与整理

目录 eBPF是什么&#xff1f; eBPF是做什么的&#xff1f;可以解决什么问题&#xff1f; eBPF可以带来的解决方案是什么&#xff1f; eBPF的技术点 eBPF hookeBPF MapeBPF Helper FunctioneBPF有什么限制吗&#xff1f; 前言 21年因为项目需求而要开发一个工具&#xff0c;可以…

每日一个小技巧:1招教你wav格式如何转换mp3

wav是一种质量较高的音频格式&#xff0c;但它的文件大小通常比较大。为了更方便地分享和存储音频文件&#xff0c;许多人都会选择将其转换为mp3格式。因为mp3格式能够在保持较高音质的同时&#xff0c;尽量降低文件大小&#xff0c;帮助你节省许多磁盘空间。那你们知道wav格式…

Java基础——多线程创建

&#xff08;1&#xff09;什么是线程&#xff1f; 线程(thread)是一个程序内部的一条执行路径。程序中只有一条执行路径&#xff0c;那么这个程序就是单线程的程序。 &#xff08;2&#xff09;多线程是什么&#xff1f; 多线程是指从软硬件上实现多执行流程的技术。 &…

让 ChatGPT 扮演一个艺术家,协助我们生成绘图 prompt

stable-diffusion Prompt 生成 直接生成 按照惯用的扮演思路&#xff0c;我们可以让 ChatGPT 扮演一个艺术家&#xff0c;协助我们生成绘图 prompt。考虑到 ChatGPT 和 DallE 同为 openai 公司产品&#xff0c;且 stable-diffusion 开源模型出现较晚&#xff0c;ChatGPT 训练…

【软件工程】UML序列图

一.概述 序列图&#xff08;时序图&#xff09;是一种软件工程行化建模方法&#xff0c;用于可视化系统或应用程序中多个对象之间 的交互。在序列图中&#xff0c;每个对象都表示为竖直线&#xff0c;对象之间的消息则表示为水平箭头 从一个对象指向另一个对象。 序列图可以…

搞懂 API ,地图 API 制作方法分享

地图 API 是一种基于 Web 开发的应用程序编程接口&#xff0c;可以用于创建和展示地图及地理信息。以下是一些地图 API 制作的方法&#xff1a; 选择地图 API 平台&#xff1a;目前市场上有很多地图 API 平台供选择&#xff0c;比如 Google Maps API、百度地图 API、高德地图 A…

2023年五月份图形化三级打卡试题

活动时间 从2023年5月1日至5月21日&#xff0c;每天一道编程题。 本次打卡的规则如下&#xff1a; 小朋友每天利用10~15分钟做一道编程题&#xff0c;遇到问题就来群内讨论&#xff0c;我来给大家答疑。 小朋友做完题目后&#xff0c;截图到朋友圈打卡并把打卡的截图发到活动群…

在阿里做测试开发的这5年,收获与感悟...

正好在离职交接空档期&#xff0c;就抽空简单分享自己的一些个人经历给大家&#xff0c;希望对刚毕业不久或者工作三五年的同学能有一些帮助。 测试新人 我的职业生涯开始和大多数测试人一样&#xff0c;开始接触都是纯功能界面测试。那时候在一家电商公司做测试&#xff0c;做…

基于异常值鲁棒性问题的极限学习机的回归问题研究(Matlab代码实现)

&#x1f4a5;&#x1f4a5;&#x1f49e;&#x1f49e;欢迎来到本博客❤️❤️&#x1f4a5;&#x1f4a5; &#x1f3c6;博主优势&#xff1a;&#x1f31e;&#x1f31e;&#x1f31e;博客内容尽量做到思维缜密&#xff0c;逻辑清晰&#xff0c;为了方便读者。 ⛳️座右铭&a…

2023年五月份图形化四级打卡试题

活动时间 从2023年5月1日至5月21日&#xff0c;每天一道编程题。 本次打卡的规则如下&#xff1a; 小朋友每天利用10~15分钟做一道编程题&#xff0c;遇到问题就来群内讨论&#xff0c;我来给大家答疑。 小朋友做完题目后&#xff0c;截图到朋友圈打卡并把打卡的截图发到活动群…

【独具匠心设计】全网最好的国学,历代文学,名著,小说网推荐

极力推荐一个功能简单、易用、访问快捷、界面大气,清爽、资源丰富、设计专业、完全免费的文学网站。它的名字叫“历代文学”&#xff0c;是由成都心海科技公司所研发&#xff0c;设计真可谓独具匠心。 “历代文学”收录了来自古今中外 20 多个朝代&#xff0c;近 30个 国家的作…

消息队列选型

消息队列选型 大家好&#xff0c;我是易安&#xff01;今天我们聊下消息队列常见选型。 消息队列作用 谈选型之前我们先讲下我们为什么需要消息队列。 消息队列是一种很流行的技术&#xff0c;自从系统间开始通信时&#xff0c;消息队列就出现了。然而&#xff0c;对消息队列给…

Windows 远程桌面提示没有远程桌面授权服务器可以提供许可证

可参考之前发布的一篇文章&#xff0c;帮助你远程登录&#xff1a;远程连接提示 由于没有远程桌面授权服务器提供许可证_计算机没有远程桌面客户端访问许可证_csdn_aspnet的博客-CSDN博客 虽然上述文章命令可以远程进入系统&#xff0c;但是每次都需要使用上述文章中的命令进入…

【数据库】索引和事务

目录 1.索引 1.1关于索引 索引是什么&#xff1f; 为什么要有索引&#xff1f; 索引的作用&#xff1f; 索引的优点和缺点&#xff1f; 1.2索引类型及创建 索引的分类 创建索引 1.3索引的数据结构 1.4索引覆盖 2.事务 2.1关于事务 概念 事务的使用 2.2事务的特…