JavaScript和ABAP的尾递归

简介: JavaScript和ABAP的尾递归

Before we start to research tail recursion, let’s first have a look at the normal recursion.

A simple factorial implementation by recursion:image.png

Let N = 5, see how new stack frame is created for each time of recursive call:


image.png


We have two stack frames now, one stores the context when n = 5, and the topmost one for current calculation: n = 4


image.png


image.png


Now since n equals to 1, we stop recursion. The current stack frame ( n = 1 ) will be poped up, the frame under it will be activated and become the topmost frame, with calculated result 1 passed into.


image.png


image.png



key note for normal recursion: during recursion, every generated stack frame is needed and could not e destroyed until the final result is calculated. The calculation is actually not started until the recursion reaches the end ( the condition n === 1 fulfills ). If N is a big integer, it will lead to huge number of stack frames and finally the “stack overflow” or “out of memory” is inevitable.


tail recursion

Source code below:

image.png

There are two biggest differences compared with normal recursion:

(1) A new internal function tailFactorial is introduced here.

(2) The calculation is actually now spread within every recursive stack frame. Each frame finishes one part of calculation and pass the current result to the next frame. Once the current stack frame finishes its task, it is actually not needed any more. And thus for example the model browser can then do some optimization on those useless stack frames.

Observe the stack frame for tail recursion step by step:



image.png


image.png


image.png



stack popped up:


image.png


When N = 20, the tail recursion has a far better performance than the normal recursion:


image.png


Update 2016-01-11

Tail recursion implementation via Scala:


image.png


The interesting thing is, after the Scala code is compiled into Java Byte code, compiler will eliminate the recursion automatically:


image.png


Tail Recursion in ABAP

First this is the normal recursion:

image.png

And here comes tail recursion version:

image.png

相关文章
|
9月前
|
JavaScript 前端开发 API
如何使用 JavaScript 代码连接部署在 SAP ABAP 服务器上的 OData 服务试读版
如何使用 JavaScript 代码连接部署在 SAP ABAP 服务器上的 OData 服务试读版
|
XML Web App开发 监控
使用 JavaScript 上传 PDF 和 Excel 等二进制文件到 ABAP 服务器并进行解析
使用 JavaScript 上传 PDF 和 Excel 等二进制文件到 ABAP 服务器并进行解析
466 0
使用 JavaScript 上传 PDF 和 Excel 等二进制文件到 ABAP 服务器并进行解析
|
Web App开发 存储 监控
不使用任何框架,手写纯 JavaScript 实现上传本地文件到 ABAP 服务器
不使用任何框架,手写纯 JavaScript 实现上传本地文件到 ABAP 服务器
170 0
不使用任何框架,手写纯 JavaScript 实现上传本地文件到 ABAP 服务器
|
JavaScript 前端开发
使用ABAP和JavaScript代码生成PDF文件的几种方式
使用ABAP和JavaScript代码生成PDF文件的几种方式
使用ABAP和JavaScript代码生成PDF文件的几种方式
|
存储 分布式计算 算法
JavaScript, ABAP和Scala里的尾递归(Tail Recursion)
这是Jerry 2021年的第 12 篇文章,也是汪子熙公众号总共第 283 篇原创文章。 今天是2021年1月20日,看看历史上的今天都发生了什么。 2004年1月20日,第一个公开版本的Scala发布。
JavaScript, ABAP和Scala里的尾递归(Tail Recursion)
|
前端开发 JavaScript Java
ABAP和JavaScript的懒加载,单例和桥接模式的实现和比较
ABAP和JavaScript的懒加载,单例和桥接模式的实现和比较
ABAP和JavaScript的懒加载,单例和桥接模式的实现和比较
|
JavaScript 前端开发
两种使用JavaScript触发ABAP事件的技术手段
两种使用JavaScript触发ABAP事件的技术手段
128 0
两种使用JavaScript触发ABAP事件的技术手段
|
JavaScript 前端开发
JavaScript和ABAP的尾递归
JavaScript和ABAP的尾递归
106 0
JavaScript和ABAP的尾递归
|
JavaScript 前端开发 Scala
通过阶乘的例子,练习在JavaScript, Scala和ABAP里实现尾递归(Tail Recursion)
通过阶乘的例子,练习在JavaScript, Scala和ABAP里实现尾递归(Tail Recursion)
93 0
通过阶乘的例子,练习在JavaScript, Scala和ABAP里实现尾递归(Tail Recursion)