0

Would this function use tail recursion?

function doStuff(param) {
  if (someExitCondition) {
    return [];
  }
  // maybe manipulate param somehow
  return [...doStuff(param - 1), value]; // spread the recursive function's result and append 1 item.
}

If not, is it possible to refactor it such that it can use tail recursion?

I suspect the fact that the result of the recursive function has an unknown size prevents tail recursion from being possible here, but I'm not certain on that.

N.B. In my case the maximum iterations is likely to be low and thus the impact of tail recursion would be negligable or possibly even 0? Thus I would class this as a premature microptimisation.

So this is mostly an academic question for which I am curious about the answer.

DJL
  • 2,060
  • 3
  • 20
  • 39
  • I haven't managed to get JavaScript to be tail recursive at all. At least not in the browser. See, https://stackoverflow.com/questions/37224520/are-functions-in-javascript-tail-call-optimized – The Fool Aug 26 '21 at 16:02
  • Side note: `...` isn't an operator. Operators can't do what `...` does. It's primary syntax. – T.J. Crowder Aug 26 '21 at 16:08
  • I wonder if tail recursion happens for generators? `function *doStuff(param) { if (param < 1) return; yield param; yield* doStuff(param-1); } console.dir([...doStuff(5)]);` (I'm aware of [this](https://stackoverflow.com/questions/30135916/does-es6-tail-call-optimization-cover-generators)) – Wyck Aug 26 '21 at 16:24

1 Answers1

1

The call to doStuff isn't in the tail position, so no, that wouldn't benefit from tail-call optimization. The order of operations at the end there is something along these lines (skipping some details):

  • Start creating the array
  • Evaluate param, subtract one from it, evaluate doStuff, and call the resulting function with the value from param - 1
  • Get the iterator from its return value
  • Loop through the values provided by that iterator adding them to the array
  • Evaluate value and add the resulting value to the array
  • Return the array

Also note that TCO isn't implemented in most JavaScript engines (despite being part of the spec), and isn't likely to be; details in my other answer here and in the answers to this question.

T.J. Crowder
  • 1,031,962
  • 187
  • 1,923
  • 1,875
  • Pretty much what I figured on the order of operations, assuming that the code is taken literally. But I know that optimisers sometimes manipulate the order of operations to take advantage of optimisations. But if course if TCO isn't even implemented then there's not much point! This isn't something I was aware of and I'm surprised given the amount of JS related content that explains how useful it is. – DJL Aug 26 '21 at 20:23