关于javascript:JavaScript-ABAP和Scala里的尾递归Tail-Recursion

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

明天是 2021 年 1 月 20 日，看看历史上的明天都产生了什么。

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

Scala 是一种采纳动态类型零碎的编译型语言，具备很强的可扩展性(Scalability)，这也是其名称的由来。

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

Jerry 没有在 SAP 规范产品开发中应用过 Scala，只是实现 2015 年公司一个外部培训安排的课程作业中，应用 Scala 在 Spark 上开发了一个最简略的 demo：统计海量英文图书里，计算出应用频率最高的十大单词。

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

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

顾名思义，如果一个函数中递归模式的调用，呈现在函数的开端，且除了该递归调用外，不蕴含其余的运算操作，则咱们称该递归函数是尾递归函数。

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

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

而尾递归版本中，第 14 行函数开端(黄色)，仅仅蕴含函数自身的递归调用，所以整个函数 tailFactorial 是一个尾递归函数。

尾递归函数存在的意义是什么呢？要答复这个问题，咱们能够先在单步调试模式下，察看惯例递归函数的执行过程。

咱们首先应用惯例递归函数，计算 5 的阶乘。

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

留神察看下图的 Call Stack 列表，此时咱们曾经有两个 factorial 函数的调用栈帧了。

什么是栈帧？温习一下大学计算机原理学到的常识：在函数执行过程中，每一个函数调用都会把以后函数的调用信息和外部变量保留在栈外面，称为一个栈帧(Stack Frame).

其中下图序号为 1 的栈帧，保留了 n = 5 的计算上下文；序号为 2 的栈帧即以后最顶层的栈帧，保留了 n = 4 的计算上下文。

因为只有当 n = 1 时递归才会完结，而以后 n = 4，所以持续单步调试第 7 行：又生成了一个 n = 3 的栈帧：

n = 2：

终于咱们来到了 n = 1 的上下文。看下图 Call Stack 里的栈帧列表，最顶层的栈帧代表以后 n = 1 的计算上下文。此时咱们曾经晓得 n = 1 的阶乘后果如何计算了，即为 1 自身。

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

此时只剩 4 个栈帧了，最顶层代表 n = 2 的栈帧。因为当初 1 的阶乘后果曾经进去了，所以 2 的阶乘后果也能计算了，为 2 乘以 1.

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

4 的阶乘计算，此时只剩两个栈帧：

5 的计算结果，回到最后最先被压到堆栈底部的 n = 5 的栈帧。计算结束，5 的阶乘为 120.

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

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

下图第 20 行语句是以尾递归形式计算 5 的阶乘入口，调用尾递归函数 tailFactorial，留神函数的第二个输出参数 total，这个参数用于存储以后阶乘的计算结果。

这个尾递归函数的完结条件是，当第一个输出参数 n 为 1 时，就把第二个输出参数的值，作为阶乘运算的最终后果返回。第二个参数实际上寄存的，是以后递归调用的阶乘计算结果。

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

下图是 tailFactorial 函数外部，行将进入第一轮递归调用的栈帧：

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

留神，此时序号为 1 的栈帧曾经齐全不再须要了，因为咱们持续进行递归调用的所需信息，都曾经蕴含在第 16 行 tailFactorial 调用的两个输出参数里了，此时 n 为上一层递归调用传入的 5 – 1 = 4，total 为上一轮传入的 5 × 1 = 5. 进行下一轮递归调用，两个输出参数的值别离是 4 – 1 = 3 和 4 * 5 = 20.

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

留神，下图标号为 1 和 2 的两个栈帧，实际上不再须要了，因为要持续进行递归调用的所有输出信息，都曾经存储在标号为 3 的栈帧里了：

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

n = 1，total = 120，终于计算完结了！这就是 5 的阶乘，如何通过尾递归的形式计算出来的全过程。

咱们在标号为 5 的栈帧里失去了最终的后果，而此时尽管栈帧 1～4 还存在，但实际上曾经毫无用处了。

因为依照尾递归版本的阶乘实现，每一轮阶乘的递归计算后果，曾经通过第二个参数 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/libra…

上述文字粗心如下：

当 (C 语言) 编译器检测到尾递归调用时，并不会创立新的栈帧并压入栈中，而是用新的栈帧笼罩掉以后处于激活状态的栈帧。编译器之所以可能这样做，是因为尾递归函数里，递归调用是以后栈帧里最初一个须要执行的函数调用。被笼罩掉的栈帧自身毫无用处，不须要再保留。采纳栈帧笼罩，而不是新建栈帧的形式，极大水平上缩小了栈帧的个数，进步了递归函数的执行性能。因而，应该尽可能地去尝试应用尾递归形式实现递归函数。

一个理论的性能比拟例子：计算 20 的阶乘，二者的性能有微小差别：一般递归实现须要 10 毫秒，而尾递归实现仅仅须要不到 1 毫秒的工夫。

留神：一个递归函数是否用尾递归形式实现，和它是否享受运行时的尾递归优化，二者不是一回事，后者须要编译器的反对。

利用开发人员通过 Scala 提供的 @tailrec 注解，通知编译器，对注解润饰的办法进行尾递归优化：

如果优化失败，或者被润饰的办法基本就不是一个尾递归函数，则编译器报错：

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

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

至于 ABAP 编译器是否反对尾递归优化？我没有钻研过，我只是感觉，尾递归优化并不能算是 ABAP 编译器必须实现的需要之一。

心愿本文能帮忙大家对尾递归优化这个概念有一个最根本的意识，感激浏览。

ABAP 专题

• Jerry 的 ABAP, Java 和 JavaScript 乱炖
• ABAP 开发人员将来应该学些什么
• Jerry 2017 年的五一小长假：8 种经典排序算法的 ABAP 实现
• Jerry 的 ABAP 原创技术文章合集
• 300 行 ABAP 代码实现一个最简略的区块链原型
• 应用 Java+SAP 云平台 +SAP Cloud Connector 调用 ABAP On-Premise 零碎里的函数
• 在 SAP 云平台的 CloudFoundry 环境下生产 ABAP On-Premise OData 服务
• ABAP vs Java，蛙泳 vs 自由泳
• 聊聊 C 语言和 ABAP
• 入手应用 ABAP Channel 开发一些小工具，晋升日常工作效率
• 我用 ABAP 做过的那些无聊的事件
• 不喜爱 SAP GUI？那试试用 Eclipse 进行 ABAP 开发吧
• 应用 Visual Studio Code 编写和激活 ABAP 代码
• 你的 ABAP 程序给佛祖开过光么？来试试 Jerry 这个小技巧
• 在 SAP 云平台 ABAP 编程环境上编写第一段 ABAP 程序
• SAP 官网公布的 ABAP 编程标准
• ABAP Code Inspector 那些暗藏的性能，您都晓得吗？
• 还在用 ABAP 进行 SAP 产品的二次开发？来理解下这种全新的二次开发理念吧
• ABAP Netweaver 体内的那些寄生式编程语言
• 从 SAP 社区上的一篇博客开始，聊聊 SAP 产品命名背地的那份情怀
• 云端的 ABAP Restful 服务开发
• 如何在 SAP 云平台 ABAP 编程环境里把 CDS view 裸露成 OData 服务
• 应用 abapGit 在 ABAP On-Premises 零碎和 SAP 云平台 ABAP 环境之间进行代码传输
• 30 分钟用 Restful ABAP Programming 模型开发一个反对增删改查的 Fiori 利用
• Jerry 带您理解 Restful ABAP Programming 模型系列之二：Action 和 Validation 的实现
• Jerry 带您理解 Restful ABAP Programming 模型系列之三：云端 ABAP 利用调试
• SAP 云平台上的 ABAP 编程环境里如何生产第三方服务
• ABAP 开发者上云的时候到了 – 当初大家能够收费应用 SAP 云平台 ABAP 环境的试用版了
• 学而不思则罔 – SAP 云平台 ABAP 编程环境的由来和实用场景
• SAP 云平台里的三叉戟利用
• 如何基于 Restful ABAP Programming 模型开发并部署一个反对增删改查的 Fiori 利用
• SAP 2019 TechEd Key Note 解读：云时代下 SAP 从业人员如何做二次开发？
• 有哪些 ABAP 关键字和语法，到了 ABAP 云环境上就没方法用了？
• ABAP 开发环境终于反对以驼峰命名法主动格式化 ABAP 变量名了
• 利用 ABAP 740 的新关键字 REDUCE 实现一个理论工作工作
• 一段让人瑟瑟发抖的 ABAP 代码
• 昨日万圣节 ABAP 怪兽级代码谜团，颁布答案啦
• 介绍一种在 ABAP 内核态进行内表高效拷贝的办法
• 应用 SAP Cloud Application Programming 模型开发 OData 的一个理论例子
• 当 ABAP 遇见普罗米修斯
• 应用 ABAP 绘制可伸缩矢量图
• ABAP 开发环境语法高亮的那些事儿
• SAP 谬误音讯调试之七种武器：让所有的谬误音讯都能被定位
• 应用 ABAP 操作 Excel 的几种办法
• SAP GUI 里的收藏夹事务码管理工具
• SAP GUI 和 Windows 注册表
• 有了 Debug 权限就能干坏事？小心了，你的一举一动尽在系统监控中
• ABAP CCDEF, CCIMP, CCMAC, CCAU, CMXXX 这些东东是什么鬼
• 实现 ABAP 条件断点的三种形式
• 应用 SAT 跟踪监控从浏览器关上的 SAP 利用的性能和调用栈
• 一个 13 年 ABAP 老兵的倡议：理解这些基础知识，对 ABAP 开发有百利而无一害
• SAP ABAP Netweaver 容器化, 不可能实现的工作吗？
• SAP 产品加强技术回顾
• SAP API 开发方法大全
• 浅谈 Java 和 SAP ABAP 的动态代理和动静代理，以及 ABAP 面向切面编程的尝试
• SAP ABAP 应用服务器的 HTTP 响应状态码(Status Code)
• SAP ABAP 里存在 Java List 这种汇合工具类么？CL_OBJECT_COLLECTION 理解一下
• ABAP 面试题系列：写一组会呈现死锁 (Deadlock) 的 ABAP 程序
• SAP ABAP Netweaver 服务器的规范登录形式解说
• SAP ABAP 关键字语法图和 ABAP 代码主动生成工具 Code Composer
• SAP ABAP SM50 的另类用处 – ABAP 工作过程对数据库表读取操作的检测
• 对于 SAP ABAP 字符变量和字符串变量字符个数的一个知识点，和一个血案
• SAP ABAP 一组关键字 IS BOUND, IS NOT INITIAL 和 IS ASSIGNED 的用法辨析
• SAP ABAP 和 Java 里的弱援用 (WeakReference) 和软援用(SoftReference)
• SAP AMDP 介绍 – ABAP 托管的 HANA 数据库过程
• 给你的 ABAP 对象打上标签(Tag)
• 历史上的明天：编程语言中 null 援用的十亿美元谬误

更多 Jerry 的原创文章，尽在：” 汪子熙 ”: