Recursion optimization in JS - where is it? PTC, TCO and FUD
Tags: javascript, webdev, node, ecmascript
Published: 2019-08-18 21:43:10

---
title: Recursion optimization in JS - where is it? PTC, TCO and FUD
published: true
description: Explaining why recursion optimization are not widely available in JS yet
tags: javascript, webdev, node, ecmascript
---

ES6 is old news by now. It's fully implemented across all modern browsers. Nothing to see here.
The compat-table of ES6 by kangax that we used to check to see progress should be all green by now, right?

Well, it's not.

![ES6 compat](https://thepracticaldev.s3.amazonaws.com/i/wdk8tparph1j8ej0dgob.png)

The proper tails call section, (tail call optimization) is red.

Why? is it a feature that can't be implemented for JS?
Well, no. There is one browser that implemented this feature. Safari.

Then it is possible, and it is out for large audience in Safari. Why does chrome and firefox lagging behind?

The answer is complicated. And as it seems from my browsing in many many bug trackers comments for V8, Firefox JS engine, github issues, TC39 committee discussions and more - also very political and opinionated.

I'll try to give here a bit of background on the subject, that may hopefully leave you knowing more why is this so hard.

### PTC? TCO?
PTC - proper tail call
TCO - tail code optimization
These 2 terms are not the same. And it is important to understand the difference between them for the discussion ahead.

### Assumptions moving forward
I don't want to make this article a primer on recursions and call stacks.
I will assume you already know about that part. In case you don't, [freecodecamp](https://www.freecodecamp.org/news/how-recursion-works-explained-with-flowcharts-and-a-video-de61f40cb7f9/) have a great article regarding this.

### Proper Tail Call
I'll say before starting, proper tail call is what should have been implemented in ES6, and not tail code optimization (which we will talk about later).
It is in the [ES6 Standard document](https://www.ecma-international.org/ecma-262/6.0/) and if you can't read the [Formal definitions](https://www.ecma-international.org/ecma-262/6.0/#sec-tail-position-calls) of it (don't worry, neither can I) you can just look at the introduction:
```
Goals for ECMAScript 2015 include providing better support for [...].
Some of its major enhancements include modules, class declarations, [..]
and proper tail calls.
```

Proper tail call is a technique where the program will not create additional stack frames for a recursion that fits the tail call definition.
This, and this only is the proper tail call value proposition.

So, instead of having a recursion with all its stack saved in memory, we will have just one level of stack saved, optimizing the recursion stack.

But how can it be? Tail recursion functions basically keep passing all the necessary data it needs down the recursion, so you don't have to rely on the stack.

The classic example here is the Fibbonaci function.

Consider this in the classic (head) recursion:
```javascript
function factorial(n) {
  if (n === 0) {
    return 1
  }
  return n * factorial(n - 1)
}
```

It has to rely on the stack on each step, as each step have to be "processed up" to the `n * factorial(n - 1)`.

Now consider this tail recursive version:
```javascript
function factorial(n, acc = 1) {
  if (n === 0) {
    return acc
  }
  return factorial(n - 1, n * acc)
}
```

In this version, we have an accumulator as an argument. This keeps track of the total so far. Therefore, the stack here have no use, all the data is available all the way down the recursion call.

Great! Recursive programming that is sometimes easier to grasp than the iterative alternative without the call stack problem. They are basically equivalent!

Only, they are not. Not in the PTC case.
The problems with PTC are [described beautifully](https://github.com/tc39/proposal-ptc-syntax#issues-with-ptc) on a recent proposal for TCO in Ecmascript.

Basically, this is what they are:
- Performance issues. This only optimize the call stack, not the calls themselves.
- Debugging. The call stack will be tempered with unnaturally, a thing that might make debugging much harder.

Yicks. No wonder people are so passionate about their positions on this regard.
Some say the debugging issues is a deal breaker, and the performance issues will kill profiling. Others disregard this as FUD, since Safari implemented PTC and hell is still closed.

You can find adults fight passionately for what they believe here:
https://github.com/tc39/proposal-ptc-syntax/issues/23
https://bugs.chromium.org/p/v8/issues/detail?id=4698

### Tail Call Optimization
Tail call optimization to the rescue!
Well, not really but I wanted to be dramatic.

Tail code optimization is different by the fact that it does not simply eliminate the additional stack calls, it completely re-compiles the recursive function to be an iterative one.

Behind the scenes, tail code optimization takes a recursive function and generate an iterative function, using `goto` internally, and then runs it.

It does not limit the stack calls, because there are none once the function is actually not recursive behind the scenes.

This solves the performance issues perfectly.
[Lua actually has this implemented long ago](http://lua-users.org/lists/lua-l/2010-02/msg00582.html) and it works perfectly. A recursive function is identical in performance to its equivalent iterative function.

### Alright, so why not just implement TCO?
Well... There is much debate about that too.
There are people who want "implicit" TCO - that is, when it recognizes a fit function for tail optimization - just do it in place.

And there are people who want "explicit" TCO - do this only if it is the developer intent by purpose.

This is what the [current proposal for Syntactic Tail Calls](https://github.com/tc39/proposal-ptc-syntax) is all about.

It introduces new syntax and new keyword for tail calls optimizations, namely the `continue` keyword.

And, again, much controversy here too it seems.
- Will we have to beg third-party library owners to re-write their code?
- The new syntax required will basically kill the feature before anyone will use it.
- etc' etc'.

So, that's the story of tail call optimization in JS as it stands right now.
I didn't go too deep on the details, ofcourse, but I feel like this should give you a basic understanding on why this subject is complicated and hard to get right.
And as always - thank you to all the guys working on this subject and the Ecmascript proposals. Your work and passion-full discussions ends up benefit us all.