How can I get TypeScript to perform Tail Recursion Optimization?

user_10365325 0
Viewed 532
const isPositive = (n: number) => n > 0;

function fitsIn(dividend: number,
                divisor: number,
                count: number,
                accum: number): number {
  if (accum + divisor > dividend) {
    return count;
  }
  return fitsIn(dividend, divisor, count + 1, accum + divisor);
}

function divide(dividend: number, divisor: number): number {
  let timesFits = fitsIn(Math.abs(dividend), Math.abs(divisor), 0, 0);
  return isPositive(dividend) === isPositive(divisor) ? timesFits : -timesFits;
}

console.log(divide(10, 3));
// 3

console.log(divide(-2147483648, -1));
// RangeError: Maximum call stack size exceeded

console.log(divide(10000, 1));
// RangeError: Maximum call stack size exceeded

I tried running this code with TypeScript 4.6.2 in Strict Mode and it caused the stack to overflow. The recursive call is at the end of the function and the accumulation is done inside the recursive function calls. Shouldn't this code be optimized for tail recursion? What should be changed to get tail recursion optimization to occur?

compiler-optimization typescript tail-recursion optimization javascript
1 Answers

TypeScript does not optimize tail-called recursive functions. See microsoft/TypeScript#32743 for an authoritative answer.

Usually the term "tail call optimization" in JavaScript denotes rewriting a tail-recursive function to an iterative version. This differs somewhat from "tail call elimination" which usually means keeping the recursion but rewriting the current stack frame instead of pushing a new one onto the stack. Both behave similarly from the outside if all you care about is stack growth, but tail call optimization generally happens at a level of abstraction higher than tail call elimination.

If you are suggesting that TypeScript implement tail call optimization as a performance improvement, that's not something that fits with TypeScript's design goals. Generally speaking if you write some code which is syntactically correct JavaScript for your target runtime environment, the compiler will emit that code as-is. TypeScript isn't supposed to optimize your JavaScript, just emit it. So there's no chance it would do this by itself.

On the other hand, you might be talking about proper tail call elimination, as introduced in the ECMAScript 2015 (ES2015/ES6) specification. This feature was intended so that JavaScript runtime engines would detect tail calls and not add to the call stack in such cases.

This feature was never widely adopted; currently only Safari-based browsers seem to consistently do this.

When runtime engine designers looked into implementing this, they ran into issues with possible performance degradation, developer confusion, etc. See this V8 blog post for example. Most runtime engines seem to have opted for a "wait-and-see" approach for some more desirable version of this, such as a syntax to explicitly opt in to such elimination. And the only notable proposal for such syntax has been "inactive" for years. So it looks like the "wait" part of "wait-and-see" might last forever.

While it would be possible for TypeScript to downlevel proper tail call elimination into something like tail call optimization, it would likely run into the same issues, and they have declined to do it.

For better or worse, it looks like automatic tail call elimination is a de-facto dead feature, and TypeScript is not going to revive it for us.

user_28872180
Related