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 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._pile (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.

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./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._pile (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.

• javascript
• node.js
• recursion
• tail-call-optimization

• You could rewrite using a while loop instead of recursion. – jfriend00 Commented Jan 15, 2017 at 21:59
• As I stated in question, I don't care about return result as callbacks are heavily async IO dependent, so using while is not possible – user704565 Commented Jan 15, 2017 at 22:56
• I'd suggest you show the actual example you're concerned about because having a function call itself from an async callback does not actually lead to stack buildup because the original function has already returned before the async callback gets called. So, we could likely help you better with your real problem if you showed your real problem. – jfriend00 Commented Jan 15, 2017 at 23:09

3 Answers 3

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), not fac(n-1). This is not a recursive tail call because the current stack still needs to remember n while puting the recursive calls so it will know which numbers to multiply.

What you can do is pute this information 1 step before:

const fac = (n, result = 1) =>
  n === 1
    ? result
    : fac(n - 1, n * result);

console.log(fac(5)); // 120

Or in terms of your code:

function fac(n, result = 1) {
  // base case
  if (n === 1) {
    return result;
  }

  // pute the next result in the current stack frame
  const next = n * result;

  // propagate this result through tail-recursive calls
  return fac(n - 1, next);
}

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.

function getPages(baseURL, startParam, endParam, progressCallback) {

    function run(param) {
         request(baseURL + param, function(err, response, body) {
             if (err) return progressCallback(err);
             ++param;
             if (param < endParam) {
                 progressCallback(null, body);
                 // run another iteration
                 // there is no stack buildup with this call
                 run(param);
             } else {
                 // indicate pletion of all calls
                 progressCallback(null, null);
             }
         });
    }
    run(startParam);
}

The prior invocation of run() has already returned and the stack has pletely 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:

function fac(n){
    var total = 1;
    while (n > 1) {
        total *= n--;
    }
    return total;
}

// run demo in snippet
for (var i = 1; i <= 10; i++) {
    console.log(i, fac(i))
}

I am not sure your recursive function has a tail call. May be you can try the following;

"use strict";
var fac = (n, r = 1) => n === 1 ? r : (r *= n, fac(n-1,r));
console.log(fac(5));