通过阶乘的例子,练习在JavaScript, Scala和ABAP里实现尾递归(Tail Recursion)
Before we start to research tail recursion, let’s first have a look at the normal recursion.
A simple factorial implementation by recursion:
function factorial(n){ if(n ===1) { return 1; } return n *factorial(n -1); }
Let N = 5, see how new stack frame is created for each time of recursive call:
We have two stack frames now, one stores the context when n = 5, and the topmost one for current calculation: n = 4
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.
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:
function tailFactorial(n, total) { if(n ===1) return total; return tailFactorial(n -1, n * total); } function factorial2(n) { return tailFactorial(n,1); }
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:
stack popped up:
When N = 20, the tail recursion has a far better performance than the normal recursion:
Update 2016-01-11
Tail recursion implementation via Scala:
The interesting thing is, after the Scala code is compiled into Java Byte code, compiler will eliminate the recursion automatically:
Tail Recursion in ABAP
First this is the normal recursion:
REPORT zrecursion. START-OF-SELECTION. DATA: lv_result TYPE int4. PERFORM fac USING 6 CHANGING lv_result. WRITE: / lv_result. FORM fac USING iv_n TYPE int4 CHANGING cv_result TYPE int4. DATA: lv_n TYPE i. cv_result = lv_n = iv_n. lv_n = lv_n - 1. IF lv_n > 1. PERFORM fac USING lv_n CHANGING cv_result. ENDIF. IF lv_n = 1. cv_result = cv_result * lv_n. ELSE. cv_result = cv_result * iv_n. ENDIF. ENDFORM.
And here comes tail recursion version:
REPORT ztail. START-OF-SELECTION. DATA: lv_result TYPE int4. PERFORM fac USING 5 1 CHANGING lv_result. WRITE: / lv_result. FORM fac USING iv_n TYPE int4 iv_acc TYPE int4 CHANGING cv_result TYPE int4. DATA: lv_n TYPE i, lv_accumulate TYPE i. IF iv_n < 1. cv_result = 1. ELSEIF iv_n = 1. cv_result = iv_acc * iv_n. ELSEIF iv_n > 1. lv_n = iv_n - 1. lv_accumulate = iv_acc * iv_n. PERFORM fac USING lv_n lv_accumulate CHANGING cv_result. ENDIF. ENDFORM.
本文来自云栖社区合作伙伴“汪子熙”,了解相关信息可以关注微信公众号"汪子熙"。
低调大师中文资讯倾力打造互联网数据资讯、行业资源、电子商务、移动互联网、网络营销平台。
持续更新报道IT业界、互联网、市场资讯、驱动更新,是最及时权威的产业资讯及硬件资讯报道平台。
转载内容版权归作者及来源网站所有,本站原创内容转载请注明来源。
- 上一篇
关于异步
一、概述 js的执行环境是‘单线程’的,异步操作是至关重要的。异步任务就是任务需要分阶段完成,各阶段可以插入其他任务,否则就是同步任务。 二、实现 js处理异步任务主要分了3个阶段: 回调函数:异步任务拆分成多个阶段的代码,将这些代码用函数包裹以便在满足条件的时候继续异步任务,该函数被称为回调函数。这样处理主要缺点是:异步任务的逻辑被拆分了,异步任务嵌套异步任务后会形成‘回调地狱’,代码耦合程度太高。 Promise和Generator:Promise是回调函数的语法糖,主要解决‘回调地狱’的问题。Generator的特性类似‘协程’,目前的实现只能说是‘半协程’,只有Generator的实例有执行权。Generator通过yield来将异步任务分阶段,每一个阶段结束都会保留当前的执行上下文,调用next方法执行下一个阶段。缺点就是需要手动执行next,错误处理有些破坏结构。 async:async函数是Generator的语法糖,结合Promise将Generator自动化并返回Promise实例,通过await来分阶段,缺点是会阻塞,错误处理没有优化。 三、总结 现在Generat...
- 下一篇
Spring框架里注解@Autowired的工作原理
Suppose I have a bean named HelloWorld which has a member attribute points to another bean User. With annotation @Autowired, as long as getBean is called in the runtime, the returned HelloWorld instance will automatically have user attribute injected with User instance. How is this behavior implemented by Spring framework? (1) in Spring container implementation’s refresh method, all singleton beans will be initialized by default. When the HelloWorld bean is initialized: Since it has the followin...
相关文章
文章评论
共有0条评论来说两句吧...
文章二维码
点击排行
推荐阅读
最新文章
- Linux系统CentOS6、CentOS7手动修改IP地址
- SpringBoot2编写第一个Controller,响应你的http请求并返回结果
- Hadoop3单机部署,实现最简伪集群
- CentOS7安装Docker,走上虚拟化容器引擎之路
- Docker使用Oracle官方镜像安装(12C,18C,19C)
- CentOS7编译安装Cmake3.16.3,解决mysql等软件编译问题
- CentOS7编译安装Gcc9.2.0,解决mysql等软件编译问题
- SpringBoot2全家桶,快速入门学习开发网站教程
- CentOS8编译安装MySQL8.0.19
- CentOS8,CentOS7,CentOS6编译安装Redis5.0.7