Intro to Recursion - Detecting an Infinite Loop

Shane Osbourne
InstructorShane Osbourne
Share this video with your friends

Social Share Links

Send Tweet
Published 8 years ago
Updated 5 years ago

When using recursion, you must be mindful of the dreaded infinite loop. Using the recursive function that we’ve built up over the previous lessons, we look at how a simple duplicated configuration item could cause chaos for our program as it has no context of which items it has previously seen. We fix this problem by introducing a parents array, which can keep track of which top-level commands have already been accessed.

Recursive functions can sometimes lead you down the dreaded path of an infinite loop. The conditional that we've been using in the previous lessons is to check the current item to see if it exists as a key on the config object. If it does we continue with the recursive loop, if it doesn't exist, that is our exit strategy and we add the current item to an array and return. When we pass build as our command, and we begin iterating over this array, we see JS and then begin iterating over this array.

So what would happen if I made a mistake here and added build again there? Well let's see what happens if we try to run this. You see maximum callbacks exceeded. So when this first runs with build as our input, next is equal to the string build which does exist here, and we call this again with this array. The same thing repeats, and we end up looking at lint, uglify, and then build, but when we hit build, this block of code actually runs again, passing back in the original array that we started with.

That's the infinite loop. So what we really need to do is have some sort of strategy in place that allows us to detect if the current configuration that was given will eventually result in an infinite loop, then we can stop this happening and give a warning to the user. To do this, we need to keep track of which top level commands have previous been seen and accessed. We can use a simple array to do this. So if we just plan this out, if we had an array called parents, that would be initially empty.

On the first run through of this function, when we pass in an array with just build, inside this loop when we're looking at the next value which is the string build, and we see that it does exist here, because we also call this again we can class this current value as something we've previously seen. So at this point, we want parents to be equal to build. The same thing would then happen with the next array, as we see JS, we'd be here again, and we'd want to add to this array JS.

So as we dig into these arrays, we need to build up some history of which top level commands we've previously seen. Then during our loop, we can query this array to say has the current item that we're looking at, already been accessed? That will be our detection. So to go about this, we could actually have another array that we pass in here, but the signature to this function is getting a bit weird now, so let's just keep it down to import.

We'll swap this around, have the import first, the initial and then we'll call this array parents. What we'll do is we'll do a simple initialization here that will handle the first time these are called. So it's either going to be equal to the initial value if it's an array that's passed in, or equal to an empty array. Do the same thing with parents, so now on the first call neither of these two items will be defined. So we sent them to an empty array.

Now to use them inside this loop we need to change this around so the input comes first, then the value that we're building up which is previous, and finally we send in parents. Except we concat onto it, the item that we're currently looking at. So in the very first run through when we have this array with build in it, this will run, only this time when we call get tasks again, we're adding the current item which is first build then JS onto this parents array.

So that's how we build up the history of what we've previously seen. So that now inside of here, we can simply say if parents index of next is greater than -1, so does the current item you're looking at exist in the array of parents that you've already seen, if it does, right now we'll just throw a new reference error and say, "Infinite loop detected." So instead of letting the program blow up, we have now detected that we have an infinite loop.

This means the config has been provided in an incorrect way, and we can do something else about it. If you don't want to throw an error, you could actually just return the previous value and ignore it, then inside of here you could put some logging or some other way of handling this error. What if we logged the tasks back to the console now, you can see we have the same result as before, except it's impossible to enter into an infinite loop.

egghead
egghead
~ 6 minutes ago

Member comments are a way for members to communicate, interact, and ask questions about a lesson.

The instructor or someone from the community might respond to your question Here are a few basic guidelines to commenting on egghead.io

Be on-Topic

Comments are for discussing a lesson. If you're having a general issue with the website functionality, please contact us at support@egghead.io.

Avoid meta-discussion

  • This was great!
  • This was horrible!
  • I didn't like this because it didn't match my skill level.
  • +1 It will likely be deleted as spam.

Code Problems?

Should be accompanied by code! Codesandbox or Stackblitz provide a way to share code and discuss it in context

Details and Context

Vague question? Vague answer. Any details and context you can provide will lure more interesting answers!

Markdown supported.
Become a member to join the discussionEnroll Today