My post on recursion yesterday left some of you wanting a more, er, practical example. What's a real-world example of where one might choose recursion?
Ask and ye shall receive:
var filesystem = [{name:'/',contents:[{name:'etc',contents:[{name:'beezlebub.conf'},{name:'sshd.conf'},
{name:'named.conf'},{name:'httpd.conf'},{name:'resolv.conf'}]},
{name:'home',contents:[{name:'tom',contents:[{name:'plan.txt'},{name:'hopes.doc'},
{name:'stock_options.xls'}]},{name:'bob',contents:[{name:'rocket.jpg'},
{name:'launch.mov'},{name:'ISS.mp4'},{name:'turnip.png'}]},{name:'jill',contents:[
{name:'karate_kid.mov'},{name:'weapons_catalog.pdf'}]}]},{name:'hello.txt'}]}];
gs.log('\n' + pretty(filesystem, ''));
function pretty(arr, pad) {
var answer = '';
for (var i = 0; i < arr.length; i++) {
var item = arr;
answer += pad + item.name + '\n';
if (item.contents)
answer += pretty(item.contents, pad + ' ');
}
return answer;
}
The code above shows a recursive traversal through a tree-structured set of data. In this example, the data represents a file system's hierarchy of directories and files. The filesystem variable is loaded with a JSON object literal — if this is new to you, read the preceding link.
The function pretty() is where the recursive traversal takes place. The test code just preceding the function definition simply calls the pretty() function with the filesystem variable and an empty string. The result (try running it in System Definition → Scripts - Background on your instance) is a nicely formatted outline-style listing of the file system.
Inside the pretty() function, the for loop iterates through all the elements of the parameter arr, which contains the elements in the directory we're traversing. Initially this is the array of file system roots, but later you'll see that this could be any directory. For each of the elements in the directory, we emit the pad (which starts off as an empty string) and the element's name. Then comes the recursive part: we look to see if the item has a contents property. If it does, then it's a directory — and we recursively invoke the pretty() function. Note carefully the two arguments to the recursive invocation: the first argument is the array with the contents of the directory we just encountered, and the second variable is the pad argument we got, plus three spaces. Those three added spaces are what indents each level of the hierarchy correctly.
It would be entirely possible to write this same function without recursion — but I don't think you're likely to do so with as little (or as simple) code. Tree traversal is a classic case for using recursion. There are lots of places in Service-now.com where we do something like this, but one that you can easily look at is in the script include JSUtil. Inside that script include, you'll find a function (actually, a method) named logObject. That was a bit too involved to use here as an example — but if you take a look at how that works, and you'll see a real-world example of recursion in action.
