4

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.

Improve this question
3
  • You could rewrite using a while loop instead of recursion. 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 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. Commented Jan 15, 2017 at 23:09

3 Answers 3

Reset to default
8

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 computing the recursive calls so it will know which numbers to multiply.

What you can do is compute 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;
  }

  // compute 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:

Proper Tail Calls in Chrome Canary

Improve this answer
Sign up to request clarification or add additional context in comments.

12 Comments

Well, but this is quite interesting, console.trace is able to print stack frames through current execution passed you said, it prints 1000 lines when I do fac(1000) using code provided by you.
And that means it has to be stored inside RAM somewhere taking useless space and if I made fac(1000000000), I would probably end up with at least 4GB RAM being used, which is very inefficient, correct me if I am wrong
Or is stack trace limited only to remembering last 10 steps?
Then what is use of tail-call optimisation in your example if I end up with stack trace being stored in RAM anyway taking place? Just purely theoretically, of course practically it will never reach over 20MB hopefully
To see if you actually have tail recursion optimization, call fac(10) and set a breakpoint inside the function and look at the stack trace when n has gotten down to 5 and see if you have stack buildup or not by looking at the current stack.
|
3

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 completion of all calls
                 progressCallback(null, null);
             }
         });
    }
    run(startParam);
}

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:

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))
}

Improve this answer

3 Comments

Sometimes this is not possible when callback function is async IO dependent
@jakubinf - Well, it depends upon what exact code you're talking about. Repeatedly calling the same function from an async callback does not result in any stack buildup so there's no problem to solve there either. While it looks like a recursive call to the eye, the stack has already unwound and the original function returned before the function is called again so in terms of stack buildup, it's not really recursion.
@jakubinf - I added more info to my question about the "async recursion" case.
1

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));

Improve this answer

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.