tail call optimization javascript

Question

NOTE: This is just for studying and bettering myself. I know of the available sort method for arrays. I'm just trying to get the basics of TCO down.

Currently trying to work on a sort algorithm using recursion. However when I try to process large datasets (+4000 objects), I am still getting a stack overflow error. I'm trying to implement TCO. I'm fairly new to the concept but I think I have the gist of it. However, I'm still receiving a stack overflow error.

const sort = (arr, counter) => {
  if (!counter) {
    counter = arr.length - 1;
  }
  for (let n = 1; n <= counter; n++) {
    if(arr[n - 1] < arr[n]) {
      let placeHolder = arr[n];
      arr[n] = arr[n - 1];
      arr[n - 1] = placeHolder;
    }
  }
  counter -= 1;
  return counter === 0 ? arr : sort(arr, counter);
};

function sortRecursive(arr) {
  return sort(arr);
}

UPDATE:

I managed to get it working, but I don't quite understand why. I managed to handle 100,000 recursions with no problems. I had to move the boolean that checks if counter is defined. However, I do not quite understand why that made it work.

const sort = (arr, counter) => {
  if (!counter) {
    counter = arr.length - 1;
  }
  for (let n = 1; n <= counter; n++) {
    if(arr[n - 1] < arr[n]) {
      let placeHolder = arr[n];
      arr[n] = arr[n - 1];
      arr[n - 1] = placeHolder;
    }
  }
  counter -= 1;
  if (counter === 0) {
    return arr;
  } else {
    return sort(arr, counter);
  }
};

function sortRecursive(arr) {
  return sort(arr, arr.length - 1);
}

OUTPUT:

let firstArr = [];
let secondArr = [];

for (let x = 0; x < 100000; x++) {
  firstArr.push(Math.ceil(Math.random() * 100000));
  secondArr.push(Math.ceil(Math.random() * 100000));
}

sortRecursive(firstArr);
//Array[100000]

Which JavaScript engine are you using? TCO is probably not actually implemented in the JavaScript engine you are using. You can verify this here. Notice that it is not in Chrome, Firefox, or any Node.js versions. — Andy Carlson
– Andy Carlson, Commented Jun 24, 2017 at 18:46
You're implementing bubble sort using recursion? Is this code you plan to use in production? JavaScript isn't defined to provide tail call optimization. Are you using a JS engine that says that it provides TCO? — JLRishe
– JLRishe, Commented Jun 24, 2017 at 18:47

Andy Ray · Accepted Answer · 2017-06-24 18:56:10Z

2

As you likely know, tail call optimization is a compiler technique that can allow a program to recurse infinitely by not allocating more memory per each recursion call.

Javascript is not currently tail call optimized, but the ES2015 standard of the language specification includes TCO. Every time a function calls itself in Javascript, a new stack frame is created, allocating new memory, so it will eventually run out and crash.

There are techniques to avoid this, including trampolines and not using a recursive loop. But at the moment you can not recursive infinitely in Javascript.

answered Jun 24, 2017 at 18:56

Andy Ray

32.3k16 gold badges114 silver badges151 bronze badges

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

2 Comments

Eddie D Over a year ago

Got it to work with TCO. Not sure why the changes I made worked though.

Michael Geary Over a year ago

I don't think they did work. See the test case in my answer. It indicates no TCO is happening.

Jonas Wilms · Accepted Answer · 2017-06-24 19:00:37Z

0

Why do you need recursion ( it will never work with 4000+ elems as this exceeds every call stack)?? cant you do:

const sort = (arr) => {
     var counter = arr.length;
     while(counter-->0){
       for (let n = 1; n <= counter; n++) {
           if(arr[n - 1] < arr[n]) {
              let placeHolder = arr[n];
              arr[n] = arr[n - 1];
              arr[n - 1] = placeHolder;
           }
        }
     }
     return arr;
}

If you want kind of recursion, you could use the qeue to keep the stack empty (requires passing a callback):

setTimeout(sort,0,arr,counter);//instead of sort(arr,counter);

By the way, easier and much faster ( because its natively implemented):

arr.sort((a,b)=>a-b);

edited Jun 24, 2017 at 19:00

answered Jun 24, 2017 at 18:50

Jonas Wilms

139k20 gold badges164 silver badges164 bronze badges

4 Comments

Eddie D Over a year ago

I managed to get it to work with TCOs. I tested out 100,000 recursions. It's more so to experiment with optimization and memory consumption. I'm mainly trying to understand the concept of TCO. It'll handle massive iterations faster than a for loop.

Jonas Wilms Over a year ago

@edwin delrio why should TCO be faster than a normal for loop?? Rhinking in assembly, its basically the same..

Michael Geary Over a year ago

TCO faster than a for loop? I don't think so. TCO simply converts the tail call into a goto to the top of the function after changing any necessary variables. So at best it will be about the same as any other loop structure.

Patrick Roberts Over a year ago

And at worst, the engine doesn't even implement it, so you're stuck with a Stack Overflow.

Michael Geary · Accepted Answer · 2017-06-24 22:57:38Z

Are you sure you're getting tail call optimization?

Here's a test with your updated code. The only things I changed are:

Added 'use strict'; to put the code in strict mode. Some browsers that support TCO in the future may require strict mode to use TCO.
Added console.trace() to print the call stack on each sort() call.
Changed the test array setup to use Math.floor() instead of Math.ceil() for the reason mentioned in my comment above.
Changed the array length to 10.

Open the developer console before running the snippet and observe the call stack traces.

I tested this in the latest versions of Chrome 59.0.3071.109, Firefox 54.0, and Edge 15.15063. The stack traces from all of them show the call stack growing on each call, indicating that there is no tail call optimization.

Just for kicks, I also tried it in Chrome with length = 100000. It ran for a very long time, probably a minute or so, and then failed with a stack overflow when the stack reached a depth of about 10257 calls. For comparison, the standard sort( function( a, b ) { return b - a; } ) completed in about 5 seconds.

Here is a good article about JavaScript tail call optimization and related topics. One of the things the article mentions is that you can get TCO in node.js by using the --harmony_tailcalls command line switch along with 'use strict';.

'use strict';

const sort = (arr, counter) => {
  console.trace();
  if (!counter) {
    counter = arr.length - 1;
  }
  for (let n = 1; n <= counter; n++) {
    if(arr[n - 1] < arr[n]) {
      let placeHolder = arr[n];
      arr[n] = arr[n - 1];
      arr[n - 1] = placeHolder;
    }
  }
  counter -= 1;
  if (counter === 0) {
    return arr;
  } else {
    return sort(arr, counter);
  }
};

function sortRecursive(arr) {
  return sort(arr, arr.length - 1);
}

let firstArr = [];
let length = 10;

for (let x = 0; x < length; x++) {
  firstArr.push(Math.floor(Math.random() * length));
}

console.clear();
sortRecursive(firstArr);
//firstArr.sort( function( a, b ) { return b - a } );
console.log( firstArr );

Collectives™ on Stack Overflow

tail call optimization javascript

3 Answers 3

2 Comments

4 Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

2 Comments

4 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related