11

Why does the following recursive code cause a stack overflow if the array list is too large? How can I fix this and still retain the recursive pattern?

var list = readHugeList();

var nextListItem = function() {
    var item = list.pop();

    if (item) {
        // process the list item...
        nextListItem();
    }
};
rphv
  • 5,409
  • 3
  • 29
  • 47
Bibek Sharma
  • 3,210
  • 6
  • 42
  • 64
  • 8
    JavaScript has a very limited call stack size. I believe this should change when implementations are updated for ES6 since proper tail calls is part of the spec IIRC. To fix it, you'll need to do it in asynchronous batches, but this will make your code require a callback. –  Jul 06 '15 at 15:42
  • 1
    @squint Also, the maximum call stack on some browsers is a little over 1400. That is the case of Opera 12.17 and bellow. A solution would be to use a `setTimeout` of 1 milisecond. – Ismael Miguel Jul 06 '15 at 15:49
  • @IsmaelMiguel: Wow, had no idea it was that low for Opera. That's insane. –  Jul 06 '15 at 15:50
  • @squint It was. At the time, twitter was broken on Opera because their code had a recursion depth or around 1425 or so. Let me try to find a link – Ismael Miguel Jul 06 '15 at 15:54
  • Bonus points for not capitalizing the "stack overflow" in the question title. Very meta. EDIT: Aww, you went and changed it. – Matt Jul 06 '15 at 15:58
  • "*still retain the recursive pattern*" - why do you want that? – Bergi Jul 06 '15 at 16:00
  • 1
    You can find some browsers stack sizes here : http://stackoverflow.com/questions/7826992/browser-javascript-stack-size-limit – merours Jul 06 '15 at 16:10
  • @bipashant I recommend that you wait around 2 hours before marking an answer as accepted. Specially since I consider Jamie Barker's answer superior. And also the solution you should use. – Ismael Miguel Jul 06 '15 at 16:36
  • 1
    @IsmaelMiguel I need recursive solution and as you mentioned earlier use of the setTimeout works so I accepted the answer. – Bibek Sharma Jul 06 '15 at 16:40
  • @bipashant It is always a good idea to wait a little more. Currently, I gave this solution but someone else can come up with a way better solution. – Ismael Miguel Jul 06 '15 at 16:41
  • 1
    Okey. Please consider this time. I'll keep in mind those things. I'm new to stackoverflow so I'm learning its processes – Bibek Sharma Jul 06 '15 at 16:44
  • 1
    @bipashant You never said why you need recursion. If your example code is to be taken as-is, using Ismael's code your recursive function calling for that amount of array values can take over 200 seconds. The for loop will take about 4 seconds. http://jsfiddle.net/ef1yc3ya/ – Jamie Barker Jul 06 '15 at 16:45
  • @JamieBarker You made my day.My instructor ask me to do this using recursion but I'll suggest him your solution.Thanks for your Fiddle – Bibek Sharma Jul 06 '15 at 16:53
  • @JamieBarker: It should be plainly obvious that the code is merely a simplified example of a real-world scenario. And you're timing a very obviously unoptimized solution. You seem eager to throw out recursion, when in some cases it's a far superior approach. –  Jul 06 '15 at 17:33
  • @biphashant: The solution you accepted works, but don't plan on using it in any serious code. As an exercise, try breaking it up into batches of 500 items or so. Your instructor will be pleased. It's still too simplified, but will show the basic concept. If your instructor tells you to use recursion, ***do not*** come to him with a `for` loop. –  Jul 06 '15 at 17:33
  • @JamieBarker your benchmark is totally broken – the first test just does a loop with an iiterator and logs to the console – the second test performs array mutation via `.pop` – to test accurately the precise difference between `for` and recursion, all other factors must remain controls (the same) – Mulan Jun 08 '17 at 11:41
  • @naomik I threw it together very quickly with very limited information available at the time. If I had known it was a learning exercise rather than something aimed to be used in a production environment, I wouldn't have bothered. The OP seemed to have understand the point being made though, so who cares... – Jamie Barker Jun 08 '17 at 14:28
  • @JamieBarker I don't see what information was missing. There's a `for` loop and a recursive function – write a benchmark that keeps *everything* the same except the `for` mechanism and the recursion mechanism – *that* will tell you the time difference between two mechanisms. If there are other differences in the two cases, you won't be able to properly attribute the time cost. Ie, can you tell me if it's `Array.prototype.pop` or `setTimeout` that's responsible for the huge difference in speed? Your benchmark certainly doesn't answer this question – Mulan Jun 08 '17 at 14:46
  • @JamieBarker *"The OP seemed to have understand the point being made though ...* – what point? It sounds like the point being made is *"you never said why you need recursion [according to this test, recursion is really slow anyway, so don't use it]"*, which is totally inaccurate. – *"... so who cares?"*, I do, and you should too. Everyone that reads your comment, views your benchmark, and walks away with some understanding that recursion is fundamentally slow and unusable is just wrong – that should mean something to you. – Mulan Jun 08 '17 at 14:51
  • the answer in the [source article](https://www.toptal.com/javascript/interview-questions) and other answers on here on this page are abysmal – see my write-up on the topic here: https://stackoverflow.com/a/43596323/633183 – Mulan Jun 08 '17 at 15:41
  • @naomik so you come over here to a dead topic from 2 years ago to nitpick and get all OCD about a quick code example not being 100% bang on perfect. Do you have *no* experience of being a developer? The point was, if you just have to iterate through an array, use a damn `for` loop. I've come across a lot of devs in my time that have automatically gone for the more complex option on things rather than the simple, more productive option. – Jamie Barker Jun 09 '17 at 10:13
  • You've also **missed** the whole point of the _example_ @naomik, it wasn't to prove that a `for` loop is better than recursion, it was to prove that **that particular** code example, i.e. **the one in the accepted answer** is inefficient. The `pop` and the `setTimeout` are **required** for the recursion to work in this instance, whereas a `for` loop **doesn't** require them. – Jamie Barker Jun 09 '17 at 10:21
  • @JamieBarker `.pop` and `setTimeout` are *not required*, which is my point – recursion is a very powerful construct used for more than just iterating thru arrays, and it's possible to use it in javascript in a stack-safe way *and* be performant simultaneously. – Mulan Jun 09 '17 at 12:18
  • So when someone comes here thinking they can fix a stack overflow problem by using `setTimeout`, what have you helped them with? They've been given a bad solution using `setTImeout`, they were told it's bad (by the author and other people), or they've been told not to use recursion and just use something else – well I'm saying you *can* use a recursion and you don't have to sacrifice performance or a synchronous return value in the process – I think that's a serious value add to the topic being discussed. – Mulan Jun 09 '17 at 12:22
  • @IsmaelMiguel, I've updated the answer to show that stone age javascript can be used to implement a trampoline that achieves 100,000,000 recursions in the same time it takes a `setTimeout` implementation to achieve just 1,000. – Mulan Jun 09 '17 at 12:57
  • "_recursion is a very powerful construct used for more than just iterating thru arrays_" - I never said it wasn't. I just said it shouldn't be used for *this*. – Jamie Barker Jun 09 '17 at 14:17
  • "_well I'm saying you can use a recursion and you don't have to sacrifice performance or a synchronous return value in the process – I think that's a serious value add to the topic being discussed_". Congratulations. You know, the average SO user (who doesn't have a god complex and goes around telling everyone their responses two years ago are a load of crap), would simply just create a new answer on the question to say "hey guys, this new tech is awesome and makes this work better". – Jamie Barker Jun 09 '17 at 14:25

3 Answers3

5

This will sound weird, but use a setTimeout.

Like this:

//fill it with 50000 elements
var list = Array(50001).join('1.1').split('.');

var nextListItem = function() {
    var item = list.pop();

    if (item) { //should be list.length

        // recursion here!
        setTimeout( nextListItem, 0 );

    }
};
nextListItem();

The recursion now is endless!

Notice that some browsers don't like that 0 there.
As a side-effect, your code won't block the browser.

Ismael Miguel
  • 4,185
  • 1
  • 31
  • 42
  • All browsers will fail on `0` or any falsey value. Since you're mutating the list, your base case should be to check `list.length`. Also, it'll be far more efficient to do a solution in batches instead of a new `setTimeout` for every item. It's never actually a `0` timer, so this could take quite a while. There are other complications too, depending on what he's actually doing. –  Jul 06 '15 at 16:24
  • @squint You are correct. I just showed what he can do to have his infinite recursion. And yes, it takes quite a while (Around 50 seconds), but the code is being executed in a non-blocking way, so, it is 'kinda' fine. – Ismael Miguel Jul 06 '15 at 16:28
  • I see the [source article](https://www.toptal.com/javascript/interview-questions) also recommends use of `setTimeout` as a solution to the stack overflow problem. **DO NOT USE `setTimeout` to solve this problem** – for more details, read my examination of the topic: https://stackoverflow.com/a/43596323/633183 – Mulan Jun 08 '17 at 15:40
  • 1
    @naomik I'm sorry, but you didn't convince me with your examination. Also, your code is doing god-know-what, while this is doing something much simpler. Also, you didn't mention that the reason why it is so slow is that browsers wait a minimum of 4 milliseconds (used to be 10) even if the timeout is 0 milliseconds. In fact, I even said it is slow (in the comment above). While your examination is valid on it's own, it doesn't matter here: all that matters is infinite recursion. And for that, this answer works just fine, in a non-blocking way. – Ismael Miguel Jun 08 '17 at 19:33
  • well I can't possibly expect to convince you of something you don't understand. And I can't possibly expect you to want to understand it. Either way, `setTimeout` is not valid solution for infinite recursion in JavaScript – Mulan Jun 09 '17 at 04:58
  • 1
    @naomik Then feel free to add your answer, keeping in mind the state of browsers' support for Promises, ES6 and all that jazz at the time. This was asked 2 years ago and a lot happened since then. In fact, no environment was specified. This means that the code can be meant to run on IE 5.5, Google Chrome 1.0, Netscape or something else. – Ismael Miguel Jun 09 '17 at 08:00
  • You can implement a trampoline using nothing but `while` and first class functions, which have been a part of JavaScript since the very beginning – *performant* infinite recursion without *necessarily* sacrificing a synchronous return value; possible as long as you knew what you were doing – the techniques I included using Promises or other ES6 features are *options*; practical implementations that you can use in a modern js program, but certainly not *requirements* – everything in my answer can be implemented in *any* version of js. – Mulan Jun 09 '17 at 12:32
  • @naomik Maybe *performant* isn't always the best. I already said: your points are very valid. A bit hard to follow, but valid. But what kills it for me is that your infinite recursion, given infinite data, will take an infinite amout of **blocking** time to the browser. Also, you can non-blocking and performant looping by doing *x* runs before a `setTimeout`. (*x* is a calculated value based on how long you have until the next "tick". I can doodle an example later on.) – Ismael Miguel Jun 09 '17 at 13:32
  • Ismael, there's nothing special about the non-blocking factor tho. If the language supports it, we can implement a non-blocking trampoline and get non-blocking, stack-safe infinite recursion *without* taking a devastating performance hit – the trick is in knowing *how* to use the language's non-blocking features correctly. I've updated the answer (yet again) to show a non-blocking trampoline that achieves 100,000,000 recursions in under 8 seconds – Mulan Jun 09 '17 at 14:31
0

Seems like you are simply looping through an array. Have you tried using a simple for loop?

var list = readHugeList();
for (var i = 0; i < list.length; i++) {
    //Do something with list[i]
}
Jamie Barker
  • 8,145
  • 3
  • 29
  • 64
  • 1
    This doesn't keep the recursion as the question requires. I'm sure he knows how a `for` loop works. –  Jul 06 '15 at 16:03
  • @squint I agree you would expect nearly all front end web developers to know what a simple for loop is, however his profile says ruby-on-rails developer. Not only that, I've come across a lot developers that try to solve simple problems with complex code more often than not, because that's just how their brain works. – Jamie Barker Jul 06 '15 at 16:13
  • Could be. Nevertheless, he specifically wanted to retain recursion *(which suggests he knows about imperative solutions)*. Not saying a `for` loop isn't sensible. Just saying it really doesn't answer the question. And frankly, there are some problems that are more easily solved with recursion. –  Jul 06 '15 at 16:21
  • 1
    @squint Well hopefully the OP will respond to **something** on here to give an indication either way. If they say "_No, I can't do that for reason: X_", then I shall remove this answer. – Jamie Barker Jul 06 '15 at 16:26
  • Yeah, I hate it when there's a discussions and everyone except the person with the question is present. –  Jul 06 '15 at 16:27
0
var taskList = breakBigTaskIntoMicroTasks(monsterTaskList);

// requestAnimationFrame will get executed in each 16ms of duration.
requestAnimationFrame(processTaskList);

function processTaskList(taskStartTime) {
    var taskFinishTime;

    do {
        // Assume the next task is pushed onto a stack.
        var nextTask = taskList.pop();

        // Process nextTask.
        processTask(nextTask);

        // Go again if there’s enough time to do the next task.
        taskFinishTime = window.performance.now();
       } while (taskFinishTime - taskStartTime < 3);
        if (taskList.length > 0)
            requestAnimationFrame(processTaskList);

}
Syscall
  • 19,327
  • 10
  • 37
  • 52
anand tiwari
  • 11
  • 3