So I recently came across case I needed to write code where callback calls itself and so on and wondered about NodeJS and tail-call support, so I found this answer https://stackoverflow.com/a/30369729 saying that yup, it's supported.
So I tried it with this simple code:
"use strict";
function fac(n){
if(n==1){
console.trace();
return 1;
}
return n*fac(n-1);
}
fac(5);
Using Node 6.9.2 on Linux x64 and run it as node tailcall.js --harmony --harmony_tailcalls --use-strict
and result was:
Trace
at fac (/home/tailcall.js:4:11)
at fac (/home/tailcall.js:7:11)
at fac (/home/tailcall.js:7:11)
at fac (/home/tailcall.js:7:11)
at fac (/home/tailcall.js:7:11)
at Object.<anonymous> (/home/tailcall.js:10:1)
at Module._compile (module.js:570:32)
at Object.Module._extensions..js (module.js:579:10)
at Module.load (module.js:487:32)
at tryModuleLoad (module.js:446:12)
Which clearly shows callstack gets filled with calls and tail-recursion isn't supported although I use latest NodeJS.
Does NodeJS/JavaScript support tail-recursion at all? Or do I really have to go with generators and yields, but problem here is my callbacks are gonna be heavily asynchronous and I'm not gonna work with return value anyway, I just need to make sure the callstack doesn't get uselessly filled with calls while function refers to itself in return.
What you have there is not a tail-call. A tail call is a function call performed as the final action of a another function. A tail-recursive call is the same except the function calls itself.
However, your code's final action is
n*fac(n-1)
, notfac(n-1)
. This is not a recursive tail call because the current stack still needs to remembern
while computing the recursive calls so it will know which numbers to multiply.What you can do is compute this information 1 step before:
Or in terms of your code:
Here's the stacktrace from Chrome Canary:
First off, if your actual case you're concerned about is when a function calls itself from an async callback, then you likely don't have any stack buildup there anyway.
That's because the original function has already returned and the whole stack unwound before the async callback gets called, so though it visually looks like recursion, there is no stack build up.
Here's a simple code example of making multiple sequenced network requests where a function calls itself from an async callback and there is no stack buildup.
The prior invocation of
run()
has already returned and the stack has completely unwound before the async callback is called so while this visually looks like recursion, there is no stack buildup.In the specific code you show, you can avoid the recursion entirely by rewriting using a while loop which would work efficiently in any version of Javascript:
I am not sure your recursive function has a tail call. May be you can try the following;