JavaScript, ABAP和Scala里的尾递归(Tail Recursion)-阿里云开发者社区

开发者社区> 开发者小助手-bz5> 正文

JavaScript, ABAP和Scala里的尾递归(Tail Recursion)

简介: JavaScript, ABAP和Scala里的尾递归(Tail Recursion)
+关注继续查看

这是Jerry 2021年的第 12 篇文章,也是汪子熙公众号总共第 283 篇原创文章。


今天是2021年1月20日,看看历史上的今天都发生了什么。


2004年1月20日,第一个公开版本的Scala发布。


image.pngimage.png

Scala是一种采用静态类型系统的编译型语言,具有很强的可扩展性(Scalability),这也是其名称的由来。


Scala设计初衷是集成面向对象编程和函数式编程的各种特性,运行于JVM平台上,并兼容已有的Java程序。


image.png


Jerry没有在SAP标准产品开发中使用过Scala,只是完成2015年公司一个内部培训布置的课程作业中,使用Scala在Spark上开发了一个最简单的demo:统计海量英文图书里,计算出使用频率最高的十大单词。


image.pngimage.png


Spark是一个使用Scala编程语言实现的专为大规模数据处理而设计的快速通用的计算引擎。本文不会讨论Spark,而是从Scala语言里,下图第11行的注解@tailrec谈起:尾递归(Tail Recursion).


image.png


每个程序员对递归的概念都耳熟能详,那什么是尾递归呢?


顾名思义,如果一个函数中递归形式的调用,出现在函数的末尾,且除了该递归调用外,不包含其他的运算操作,则我们称该递归函数是尾递归函数。


本文用阶乘算法来介绍尾递归的概念。


下图红色区域内是阶乘算法的常规递归实现,蓝色区域是阶乘算法的尾递归实现版本。在常规递归算法的末尾,第8行语句(绿色),除了递归调用factorial函数外,还包含一个同n的乘法操作,所以整个函数factorial不能算作尾递归函数。


而尾递归版本中,第14行函数末尾(黄色),仅仅包含函数本身的递归调用,所以整个函数tailFactorial是一个尾递归函数。


image.png


尾递归函数存在的意义是什么呢?要回答这个问题,我们可以先在单步调试模式下,观察常规递归函数的执行过程。


我们首先使用常规递归函数,计算5的阶乘。


输入参数n为5,执行到第7行,5的阶乘等于5乘以4的阶乘。单步调试进去,输入参数n = 5, 进入第7行,准备执行 5 * factorial(4) .


image.png


注意观察下图的Call Stack列表,此时我们已经有两个factorial函数的调用栈帧了。


什么是栈帧?复习一下大学计算机原理学到的知识:在函数执行过程中,每一个函数调用都会把当前函数的调用信息和内部变量保存在栈里面,称为一个栈帧(Stack Frame).


其中下图序号为1的栈帧,保存了n = 5的计算上下文;序号为2的栈帧即当前最顶层的栈帧,保存了n = 4的计算上下文。



image.png

因为只有当n = 1时递归才会结束,而当前n = 4,所以继续单步调试第7行:又生成了一个n = 3的栈帧:


image.png


n = 2:


image.png


终于我们来到了n = 1的上下文。看下图Call Stack里的栈帧列表,最顶层的栈帧代表当前n = 1的计算上下文。此时我们已经知道n = 1的阶乘结果如何计算了,即为1本身。


第5行代码返回1的阶乘计算结果1,这行语句返回之后,当前序号为5的栈帧就会被销毁,即将回到下一层序号为4的栈帧去。


image.png


此时只剩4个栈帧了,最顶层代表n = 2的栈帧。因为现在1的阶乘结果已经出来了,所以2的阶乘结果也能计算了,为2乘以1.

image.png



2的阶乘返回后,现在只剩3个栈帧,最顶层为n = 3的计算上下文。3的阶乘也能计算了,为3乘以前一个栈帧返回的计算结果,即2的阶乘结果,所以最后为3 × 2 = 6. 如下图所示:



image.png

4的阶乘计算,此时只剩两个栈帧:


image.png


5的计算结果,回到最初最先被压到堆栈底部的n = 5的栈帧。计算完毕,5的阶乘为120.


是不是体现出了《数据结构》教科书上关于栈“先进后出”的工作原理?


image.png


下面再来看看用尾递归实现的阶乘。


下图第20行语句是以尾递归方式计算5的阶乘入口,调用尾递归函数tailFactorial,注意函数的第二个输入参数total,这个参数用于存储当前阶乘的计算结果。


image.png


这个尾递归函数的结束条件是,当第一个输入参数n为1时,就把第二个输入参数的值,作为阶乘运算的最终结果返回。第二个参数实际上存放的,是当前递归调用的阶乘计算结果。


当n大于1时,递归尚未满足退出条件,此时首先将n和当前的阶乘计算结果(变量total)相乘,将乘积作为第二个输入参数,传递到下一层递归调用的栈帧中去。


下图是tailFactorial函数内部,即将进入第一轮递归调用的栈帧:



image.png

第一轮递归调用的栈帧内部,序号为2.


注意,此时序号为1的栈帧已经完全不再需要了,因为我们继续进行递归调用的所需信息,都已经包含在第16行tailFactorial调用的两个输入参数里了,此时n为上一层递归调用传入的5 - 1 = 4,total为上一轮传入的5 × 1 = 5. 进行下一轮递归调用,两个输入参数的值分别是4 - 1 = 3和4 * 5 = 20.


image.png


进入第三层递归调用,此时输入参数 n = 3,total = 20,均为上一层调用传入。


注意,下图标号为1和2的两个栈帧,实际上不再需要了,因为要继续进行递归调用的所有输入信息,都已经存储在标号为3的栈帧里了:


image.png


n = 2, total = 60,同理,标号为1,2,3的栈帧都不再需要了。


image.png


n = 1,total = 120,终于计算结束了!这就是5的阶乘,如何通过尾递归的方式计算出来的全过程。


我们在标号为5的栈帧里得到了最终的结果,而此时虽然栈帧1~4还存在,但实际上已经毫无用处了。


image.png


因为按照尾递归版本的阶乘实现,每一轮阶乘的递归计算结果,已经通过第二个参数total保存了下来,因此没有必要再用一个完整的栈帧,去保存当前这轮递归计算的函数调用上下文了。这就引出了所谓“尾递归优化”的概念:


When a compiler detects a call that is tail recursive, it overwrites the current activation record instead of pushing a new one onto the stack. The compiler can do this because the recursive call is the last statement to be executed in the current activation; thus, there is nothing left to do in the activation when the call returns. Consequently, there is no reason to keep the current activation around. By replacing the current activation record instead of stacking another one on top of it, stack usage is greatly reduced, which leads to better performance in practice. Thus, we should make recursive functions tail recursive whenever we can.


https://www.oreilly.com/library/view/mastering-algorithms-with/1565924533/ch03s02.html


上述文字大意如下:


当(C语言)编译器检测到尾递归调用时,并不会创建新的栈帧并压入栈中,而是用新的栈帧覆盖掉当前处于激活状态的栈帧。编译器之所以能够这样做,是因为尾递归函数里,递归调用是当前栈帧里最后一个需要执行的函数调用。被覆盖掉的栈帧本身毫无用处,不需要再保留。采用栈帧覆盖,而不是新建栈帧的方式,极大程度上减少了栈帧的个数,提高了递归函数的执行性能。因此,应该尽可能地去尝试使用尾递归方式实现递归函数。


一个实际的性能比较例子:计算20的阶乘,二者的性能有巨大差异:普通递归实现需要10毫秒,而尾递归实现仅仅需要不到1毫秒的时间。


image.png


注意:一个递归函数能否用尾递归方式实现,和它能否享受运行时的尾递归优化,二者不是一回事,后者需要编译器的支持。


应用开发人员通过Scala提供的@tailrec注解,告诉编译器,对注解修饰的方法进行尾递归优化:


image.png


如果优化失败,或者被修饰的方法根本就不是一个尾递归函数,则编译器报错:


could not optimize @tailrec annotated method fibonacci: it contains a recursive call not in tail position


用ABAP实现尾递归版本的阶乘运算:


image.png


至于ABAP编译器能否支持尾递归优化?我没有研究过,我只是觉得,尾递归优化并不能算是ABAP编译器必须实现的需求之一。


希望本文能帮助大家对尾递归优化这个概念有一个最基本的认识,感谢阅读。


版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

相关文章
使用NAT网关轻松为单台云服务器设置多个公网IP
在应用中,有时会遇到用户询问如何使单台云服务器具备多个公网IP的问题。 具体如何操作呢,有了NAT网关这个也不是难题。
25920 0
阿里云服务器如何登录?阿里云服务器的三种登录方法
购买阿里云ECS云服务器后如何登录?场景不同,大概有三种登录方式:
2503 0
阿里云服务器ECS远程登录用户名密码查询方法
阿里云服务器ECS远程连接登录输入用户名和密码,阿里云没有默认密码,如果购买时没设置需要先重置实例密码,Windows用户名是administrator,Linux账号是root,阿小云来详细说下阿里云服务器远程登录连接用户名和密码查询方法
9501 0
使用OpenApi弹性释放和设置云服务器ECS释放
云服务器ECS的一个重要特性就是按需创建资源。您可以在业务高峰期按需弹性的自定义规则进行资源创建,在完成业务计算的时候释放资源。本篇将提供几个Tips帮助您更加容易和自动化的完成云服务器的释放和弹性设置。
11017 0
阿里云服务器如何登录?阿里云服务器的三种登录方法
购买阿里云ECS云服务器后如何登录?场景不同,阿里云优惠总结大概有三种登录方式: 登录到ECS云服务器控制台 在ECS云服务器控制台用户可以更改密码、更换系.
10522 0
windows server 2008阿里云ECS服务器安全设置
最近我们Sinesafe安全公司在为客户使用阿里云ecs服务器做安全的过程中,发现服务器基础安全性都没有做。为了为站长们提供更加有效的安全基础解决方案,我们Sinesafe将对阿里云服务器win2008 系统进行基础安全部署实战过程! 比较重要的几部分 1.
8120 0
如何设置阿里云服务器安全组?阿里云安全组规则详细解说
阿里云安全组设置详细图文教程(收藏起来) 阿里云服务器安全组设置规则分享,阿里云服务器安全组如何放行端口设置教程。阿里云会要求客户设置安全组,如果不设置,阿里云会指定默认的安全组。那么,这个安全组是什么呢?顾名思义,就是为了服务器安全设置的。安全组其实就是一个虚拟的防火墙,可以让用户从端口、IP的维度来筛选对应服务器的访问者,从而形成一个云上的安全域。
6013 0
阿里云服务器如何登录?阿里云服务器的三种登录方法
购买阿里云ECS云服务器后如何登录?场景不同,云吞铺子总结大概有三种登录方式: 登录到ECS云服务器控制台 在ECS云服务器控制台用户可以更改密码、更换系统盘、创建快照、配置安全组等操作如何登录ECS云服务器控制台? 1、先登录到阿里云ECS服务器控制台 2、点击顶部的“控制台” 3、通过左侧栏,切换到“云服务器ECS”即可,如下图所示 通过ECS控制台的远程连接来登录到云服务器 阿里云ECS云服务器自带远程连接功能,使用该功能可以登录到云服务器,简单且方便,如下图:点击“远程连接”,第一次连接会自动生成6位数字密码,输入密码即可登录到云服务器上。
20957 0
2497
文章
0
问答
来源圈子
更多
+ 订阅
文章排行榜
最热
最新
相关电子书
更多
《Nacos架构&原理》
立即下载
《看见新力量:二》电子书
立即下载
云上自动化运维(CloudOps)白皮书
立即下载