Tail Call Optimization (TCO) - kdaisho/Blog GitHub Wiki

TCO has been implemented only in Safari as of Apr 2024. But what is TCO (tail Call Optimization)?

Here's a recursive function named woo. It takes a number and it returns bangs corresponds to the number argument.

woo(3) // "!!!"

1. Non-tail-recursive function

const woo = (n) => {
  if (n === 0) return "";
  return woo(n - 1) + "!";
/*            ^ not  ^ cuz does more work!
                tail
                call!
*/
}

2. Tail-recursive function

const woot = (n) => {
  const woo = (n, acc) => {
    if (n === 0) return acc;
    return woo(n - 1, acc + "!");
  }
  return woo(n, "");
/*            ^ tail ^ caz no more work!
                call!                
*/
}

Test in Chrome and in Safai

Non-tail-recursive function woo

In Chrome, a stack overflow error is thrown if the argument is more than 10000.

// Chrome: V8
woo(10000) // Uncaught RangeError: Maximum call stack size exceeded

In Safai, even non-tail-recursive function can run up to 38000.

// Safari: JavaScriptCore
woot(35000) // "!!!!!!!!..."
woot(38000) // Uncaught RangeError: Maximum call stack size exceeded

Tail-recursive function woot

In Chrome, a stack overflow error is thrown with the same count: 10000.

Because TCO is not implemented in V8.

// Chrome: V8
woot(10000) // Uncaught RangeError: Maximum call stack size exceeded

In Safai, tail-recursive function somehow ended up with the same performance with non-tail-recursive function.

🤔🤔🤔🤔