如何在JavaScript, Scala和ABAP里实现尾递
导读:本文共3572字符,通常情况下阅读需要12分钟。同时您也可以点击右侧朗读,来听本文内容。按键盘←(左) →(右) 方向键可以翻页。
摘要:在JavaScript, Scala和ABAP里实现尾递归(Tail Recursion),针对这个问题,这篇文章详细介绍了相对应的分析和解答,希望可以帮助更多想解决这个问题的小伙伴找到更简单易行的方法。Before we start to research tail recursion, let’s first have a look at the normal recursion.A simp... ...
目录
(为您整理了一些要点),点击可以直达。Before we start to research tail recursion, let’s first have a look at the normal recursion.
A simple factorial implementation by recursion:
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.
Source code below:
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:
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:
First this is the normal recursion:
And here comes tail recursion version:
如何在JavaScript, Scala和ABAP里实现尾递的详细内容,希望对您有所帮助,信息来源于网络。