|
General Details
|
|
JavaScript
|
|
Posted 147 Days Ago
|
|
180 Views
|
|
Received 2 Ratings
|
|
Tail Call Optimization
Description
A big problem in JavaScript is recursion. As a functional programming language, recursion is a natural way to express many algorithms. Unfortunately, most browsers have atrociously short function call stacks (many have a couple thousand, Safari has 100). While this exact solution is not perfect (it only works in one browser), it's an idea that can probably be translated into any modern browser.
The idea is to implement Tail Call Optimization (also known as tail-end recursion). If the last statement to be executed in a function simply calls the same function again, then there's no need to add another record to the call stack; the current record can be reused. The trick is that the recursive call must not be part of any expression. It must return simply return the result. This means that some otherwise simple recursive algorithms must be rewritten slightly to take advantage of this optimization.
The posted code contains the 3 functions required to implement Tail Call Optimization, as well as two example functions calls.
Technical
Requires Mozilla JavaScript 1.5+. Any version of Firefox will do, or try the SeaMonkey JS shell.
Source Code
Comments
| Please login to post comments. |
|
|
I like your description for this, and the codes quite nice as well. Cinjection made a
good point though. There isn't much javascript code here. I'm gonna post
some js codes when i learn more of scriptaculous.
Nice work anyway :-)
Kind regards,
Scott
|
|
|
The idea here was to let the programmer write a "recursive" function, but
let it run iteratively. Granted, this won't run as fast as if the programmer
rewrote the function as an iteration (and it wasn't the goal), but it avoids the
hassle of keeping track of local variables.
Anyway, I doubt this would ever have any practical purpose; it was really just to
see if it could be done.
|
|
|
You should generally avoid using recursion at all if you're going for
tail-recursion. All tail recursive solutions can be re-written using regular
iteration. In fact, compilers for more elegant languages will make that conversion
for you automatically.
Nice code though. I haven't seen too many submissions for Javascript.
|
More "JavaScript" Source Codes By This Author
Recently Posted "JavaScript" Source Codes
Recently Rated "JavaScript" Source Codes
|
