DEV Community

Recursion optimization in JS - where is it? PTC, TCO and FUD

Snir David on August 18, 2019

ES6 is old news by now. It's fully implemented across all modern browsers. Nothing to see here. The compat-table of ES6 by kangax that we used to c...
Collapse
 
username_80 profile image
Full Name

This article is rather confusing.

TCO is Tail CALL Optimization, not "Tail Code". Obviously, all (non-empty) functions have CODE in the tail position.

"This only optimize the call stack, not the calls themselves" makes no sense, and nobody at the PTC proposal said anything like this.

You say "The problems with PTC are described beautifully" in the linked proposal, but if you read the comments there, the people they're summarizing say it's not accurate. For example, the summary says JSC saw a perf improvement (which would be great, if true), but the JSC devs say they saw no measurable change in performance. I don't know why anyone is still mentioning performance, because I see no JS engine devs saying that's a problem (or a benefit).

You say "Tail code optimization is different [than what?] by the fact that it does not simply eliminate the additional stack calls, it completely re-compiles the recursive function to be an iterative one." I've written compilers before, and I can't tell what you mean by "completely re-compiles". Essentially all it does is replace a CALL with a GOTO so it doesn't add a new stack frame. It doesn't need to "re"-do anything, and it doesn't affect the rest of the function at all.

You say "The classic example here is the Fibbonaci function." That's not a Fibonacci function. That's not even how "Fibonacci" is spelled.

You say "Proper tail call is a technique where the program will not create additional stack frames for a recursion that fits the tail call definition." Recursion is a common use of PTC, but TCO isn't just for recursion. It applies to all calls in the tail position, not just self-calls.

You show "classic (head) recursion", but I've never heard of either of those terms before. The recursive call here clearly isn't in the head position. It's in the middle. I don't know what might be more "classic" about the head or non-tail positions, either.

Anyone who wants to learn about this subject online would do better to read the Wikipedia article for "Tail call", and the TC39 issue comments.

Collapse
 
rafaelyanez profile image
rafaelyanez

So, what has been the response of the Safari people, how did they implement proper tail calls? Douglas Crockford was saying something like it was Microsoft's fault, that they didn't want to implement the feature, and that now that they have essentially give up in the browser by the adoption for Chromium, that now we might have the change of having these feature implemented

Collapse
 
wadimhalik profile image
Wadim Halik

Why not have both? Proper Tail Calls as a standard behaviour with the option to use a keyword to tell the compiler to do Tail Call Optimization.
Or the other way around, I really don't care as long as we have it implemented already. Jeez.

Collapse
 
roninbar profile image
Ron Inbar

That's not Fibonacci...

Collapse
 
elugens profile image
Stacey Wilson

He should change that because it can confuse the noobs.

function fibonacci(num, memo) {
memo = memo || {};

if (memo[num]) return memo[num];
if (num <= 1) return 1;

return memo[num] = fibonacci(num - 1, memo) + fibonacci(num - 2, memo);
}

Collapse
 
klarkc profile image
Walker Gusmão

Amazing, I never thought that TCO could bring so many "problems", thanks for clarify.

IMHO at least PTC should be available, as it could remove many of common issues with recursive behavior in JS