What is recursionMost 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 recursionThere are 2 kinds of people in the world
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 candidatesOnce 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 WalkthroughThere's so little to this, there's not much to walkthrough - The key points are
SugarIt 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 codefunction 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
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. |
Services > Desktop Liberation - the definitive resource for Google Apps Script and Microsoft Office automation > Google Apps Scripts snippets >