JavaScript recursion primer

What is recursion

Most modern coding languages allow recursion – in other words allow a function to call itself. This concept is central to being able to deal with object structures that are linked or of indeterminate depth, and to be able to write elegant and simple solutions to complex problems.

Understanding recursion

There are 2 kinds of people in the world
  1. Those that get recursion
  2. Those that don’t
    1. Those that could learn
      1. Those that just need a little practise for the lightbulb to go off
      2. Those that need coaching
        1. Those that need lots of face to face coaching
          1. etc…
          2. etc…
        2. Those that just need some interaction
    2. Those that never will
The above example is easy to follow, even if you are one of those that don’t  get recursion yet. First think about how you would code something up to present a list like this, especially when you don’t know how many levels there may be. I’d be surprised if you didn’t find yourself thinking about a recursive solution even if you haven’t created one before and even if you think of yourself as a member of 2.2.2

Good recursion candidates

Once you’ve written a couple of your own recursive functions , you’ll instinctively recognize good recursive candidates. In fact you’ll wonder how some problems could ever otherwise be solved. A typical recursion candidate is one where you have a parent/child relationship between objects. Think of a directory (or tree) structure. Folders contain other folders, which may contain other folders or maybe files, and so on for ever. To simplify to bare bones, something that looks like this is a good candidate.
Let’s say we have something that looks like this, where children is an array of other nodes with the same structure.
Now take our example of ‘two kinds of people in the world’ and lay it out as a JSON object. This is the kind of thing you might find yourself needing to traverse when dealing with tree structures. I’ve added some names too just to complete the picture.

So how to do it ?

The beauty of recursion is that this kind of complicated structure can be traversed in just a few lines of code –  because each node is the same as each other regardless of where they fall in the hierarchy of the tree.
so this
gives this

Walkthrough

There’s so little to this, there’s not much to walkthrough – The key points are
  • Initially call the recursive function with the root as an argument to kick the whole thing off
  • process the data for this node – in this case print the label
  • loop through each child, with the function calling itself with each child as the argument. This will cause the child to be processed (label printed), and its children processed and so on until there are no more children

Sugar

It would be nicer if we were to indent each level of node, so lets add something to present it a little better. We’ll keep track of the recursion depth and indent the text to show the node depth. Here’s the result

And the updated code

Walkthrough

  • create a function that can make a string of padding of a particular length. We can use the Array.join(pad) method to join a variable number of null array elements where pad is the character to join these elements with. So in other words we’ll get a string of pad characters
  • introduce a depth argument which will be used to figure out how much indenting to do for the current depth of child nodes.
  • Just before processing the children of a node increase the indentation depth
  • after processing the children, decrease the indentation depth to that of the parent

And that’s all there is to it. Happy recursing. If this has whetted your appetite for recursion, here’s  More recursion – parents and children

For more Snippets topics, see: