Intro to Recursion - The Problem

Shane Osbourne
InstructorShane Osbourne
Share this video with your friends

Social Share Links

Send Tweet
Published 8 years ago
Updated 5 years ago

Recursion is a technique well suited to certain types of tasks. In this first lesson we’ll look at solving a problem that requires the flattening of arrays without using recursion. Showing the shortcoming of a non-recursive solution first will help you to understand why it’s so valuable and why sometimes it's the only solution to many problem.

[00:00] One of the hardest parts of learning recursion is actually knowing when it's the appropriate technique to use. In this example where I was building a task runner, it takes a configuration object like this where the key names are commands and they map to a set of tasks. So similar to gulp or grunt, the idea is that you'd be able to run gulp.js, it would notice that this is actually a command name on the left here, and it would run any tasks associated with it.

[00:33] So the first thing we would need to do is look at the input which could be multiple items here. We need to loop through these items, look if they exist as a property on a configuration object, and then add their tasks to an array. So if input is JS, we literally want this task array to equal exactly this, as both of these are tasks and not top level commands.

[01:02] If we were to run multiple commands at once, say gulp.js css, then our import would look like this, and we would need to also look at this top level command and pull out these tasks, and add them to this array. Surely the result will be something like that. Finally, we need to account for situations where the import includes both command names and task names. So for example, if we have three items here js, css, and version rev, then the import would look like this and the tasks array would look like this.

[01:47] So there's our goal. We take our input and we convert it to a flat array that no longer includes top level commands but instead includes the tasks that are associated to them. So let's strip this back and then write the code that can handle first of all running just the js command. Because our input array can have many items, we'll first loop over that.

[02:20] Then for each item we can check if it exists as a key here by saying if config task our first item being js, does exist here, so we need to access the array that's associated to it. Then we need to loop over those items and add them to this tasks array. So we can call for each on this and simply push that item onto the tasks array. If we log that to the console now, you can see we do in fact get lint and uglify. We can check that it also works with multiple input items.

[03:00] So now you can see we've taken the two tasks from the JS command, put those there, and the two tasks from the css command and put them there. Now let's look if we can also add a regular task here that isn't a command. That's not working because we're only dealing here with items that exist on this config object. So we can put an else here and push the current item onto the tasks array. There you see we get the flat array that we wanted, the two js tasks, the two css tasks, and the version rev task that is not a command.

[03:48] So now let's look at a more complicated example where we pass the build command as our input. If we run this you can see the problem. Now this tasks array only has js, css, and version rev. That's because as we entered this loop here, from this array, task becomes equal to first js, then css, then version rev, but we're simply pushing that task onto the array. When what we should really do is perform this entire check again. So we could copy that entire block, paste that in there, run it again, and it works.

[04:35] That's because the first iteration of this input array is equal to build, it exists here, so we start looping over this array, as we do that, we first see js, we look again on the config object to see if it exists, it does, so we begin looping over these two. So this is the point where lint and uglify get added to the main array. The same thing then happens to css, and then we version rev hits this section we end up in this block and it gets added there. Notice the repetition here and how brittle this code looks.

[05:21] Although it's working right now, we can break this very easily. We'll create another command called dist. This will first run everything from the build command, and then it will run a separate task deploy. We'll change our input to then be dist, and run that. You can see we have the same problem as before, where now we just have js, css, version rev, and deploy.

[05:50] To fix it, you may have guessed this, but we're going to need to copy and paste this entire block inside of here. Run it again, and you can see we've got it working. I don't need to tell you right now that this is a terrible way to write a program. It's repetitive, error-prone, and extremely limiting. So in the next lesson we'll look how to solve this type of problem using recursion.

egghead
egghead
~ 11 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