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. 

var node = { "label":"im a node", "children":[]};

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.

var root = {
    "label": "There are 2 kinds of people in the world",
    "children": [
        {
            "label": "Those that get recursion",
            "children": [
                {
                    "label": "ahmed",
                    "children": []
                },
                {
                    "label": "zoe",
                    "children": []
                }
            ]
        },
        {
            "label": "Those that don't",
            "children": [
                {
                    "label": "Those that could learn",
                    "children": [
                        {
                            "label": "Those that just need a little practise for the lightbulb to go off",
                            "children": [
                                {
                                    "label": "mike",
                                    "children": []
                                },
                                {
                                    "label": "tim",
                                    "children": []
                                }
                            ]
                        },
                        {
                            "label": "Those that need coaching",
                            "children": [
                                {
                                    "label": "Those that need lots of face to face",
                                    "children": [
                                        {
                                            "label": "jim",
                                            "children": []
                                        },
                                        {
                                            "label": "mary",
                                            "children": []
                                        }
                                    ]
                                },
                                {
                                    "label": "Those that just need some interaction",
                                    "children": [
                                        {
                                            "label": "fatima",
                                            "children": []
                                        },
                                        {
                                            "label": "tom",
                                            "children": []
                                        },
                                        {
                                            "label": "barbie",
                                            "children": []
                                        },
                                        {
                                            "label": "ken",
                                            "children": []
                                        }
                                    ]
                                }
                            ]
                        }
                    ]
                },
                {
                    "label": "Those that never will",
                    "children": [
                        {
                            "label": "statler",
                            "children": []
                        },
                        {
                            "label": "waldorf",
                            "children": []
                        }
                    ]
                }
            ]
        }
    ]
}


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

function print() {

  recursivePrint (root);
  
  function recursivePrint(node) {
    Logger.log(node.label);
    node.children.forEach(function(childNode) {
      recursivePrint (childNode);
    });
  }
}

gives this
[15-02-04 09:59:25:386 GMT] There are 2 kinds of people in the world
[15-02-04 09:59:25:387 GMT] Those that get recursion
[15-02-04 09:59:25:387 GMT] ahmed
[15-02-04 09:59:25:387 GMT] zoe
[15-02-04 09:59:25:388 GMT] Those that don't
[15-02-04 09:59:25:388 GMT] Those that could learn
[15-02-04 09:59:25:388 GMT] Those that just need a little practise for the lightbulb to go off
[15-02-04 09:59:25:388 GMT] mike
[15-02-04 09:59:25:388 GMT] tim
[15-02-04 09:59:25:389 GMT] Those that need coaching
[15-02-04 09:59:25:389 GMT] Those that need lots of face to face
[15-02-04 09:59:25:389 GMT] jim
[15-02-04 09:59:25:389 GMT] mary
[15-02-04 09:59:25:390 GMT] Those that just need some interaction
[15-02-04 09:59:25:390 GMT] fatima
[15-02-04 09:59:25:390 GMT] tom
[15-02-04 09:59:25:390 GMT] barbie
[15-02-04 09:59:25:391 GMT] ken
[15-02-04 09:59:25:391 GMT] Those that never will
[15-02-04 09:59:25:391 GMT] statler
[15-02-04 09:59:25:391 GMT] waldorf

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
recursivePrint (root);
  • process the data for this node - in this case print the label
Logger.log(node.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
node.children.forEach(function(childNode) {
  recursivePrint (childNode);
 });

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

[15-02-04 10:33:46:999 GMT] There are 2 kinds of people in the world
[15-02-04 10:33:46:999 GMT] --Those that get recursion
[15-02-04 10:33:46:999 GMT] ----ahmed
[15-02-04 10:33:47:000 GMT] ----zoe
[15-02-04 10:33:47:000 GMT] --Those that don't
[15-02-04 10:33:47:000 GMT] ----Those that could learn
[15-02-04 10:33:47:001 GMT] ------Those that just need a little practise for the lightbulb to go off
[15-02-04 10:33:47:001 GMT] --------mike
[15-02-04 10:33:47:001 GMT] --------tim
[15-02-04 10:33:47:001 GMT] ------Those that need coaching
[15-02-04 10:33:47:002 GMT] --------Those that need lots of face to face
[15-02-04 10:33:47:002 GMT] ----------jim
[15-02-04 10:33:47:002 GMT] ----------mary
[15-02-04 10:33:47:002 GMT] --------Those that just need some interaction
[15-02-04 10:33:47:003 GMT] ----------fatima
[15-02-04 10:33:47:003 GMT] ----------tom
[15-02-04 10:33:47:003 GMT] ----------barbie
[15-02-04 10:33:47:003 GMT] ----------ken
[15-02-04 10:33:47:004 GMT] ----Those that never will
[15-02-04 10:33:47:004 GMT] ------statler
[15-02-04 10:33:47:004 GMT] ------waldorf

And the updated code

function print() {

  // kick the thing off
  recursivePrint (root);
  
  function recursivePrint(node,depth) {
    
    // if we didnt get a depth, start at 0
    depth = depth || 0;
    
    // indent by double the node depth 
    Logger.log(indent(depth*2 , "-") + node.label);
    
    // indent the children a bit more
    depth++;
    
    // process the children
    node.children.forEach(function(childNode) {
      recursivePrint (childNode,depth);
    });
    
    // unindent as we're finished the children
    depth--;
  }
  
  function indent(by,pad) {
    // if there is any indentation to do, create a and array of requested length and use pad character to join
    return by > 0 ? new Array(by+1).join(pad) : "";
  }
}

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
function indent(by,pad) {
  // if there is any indentation to do, create a and array of requested length and use pad character to join
  return by > 0 ? new Array(by+1).join(pad) : "";
 }
  • introduce a depth argument which will be used to figure out how much indenting to do for the current depth of child nodes.
// if we didnt get a depth, start at 0
depth = depth || 0;

// indent by double the node depth
Logger.log(indent(depth*2 , "-") + node.label);
  • Just before processing the children of a node increase the indentation depth
// indent the children a bit more
depth++;
  • after processing the children, decrease the indentation depth to that of the parent
// unindent as we're finished the children
depth--;

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 like this, see  Google Apps Scripts snippets. Why not join our forum,follow the blog or follow me on twitter to ensure you get updates when they are available. 

You want to learn Google Apps Script?
Learning Apps Script, (and transitioning from VBA) are covered comprehensively in my my book, Going Gas - from VBA to Apps script, available All formats are available now from O'Reilly,Amazon and all good bookshops. You can also read a preview on O'Reilly. 
If you prefer Video style learning I also have two courses available. also published by O'Reilly.
 Google Apps Script for Developers and Google Apps Script for Beginners.




Comments