We have arrived at the vaunted back end. Last week in Hack Reactor Remote we tackled Node.js, which, for all its mystery, is simply a browser-free runtime environment for JavaScript. With which you can do…amazing things. We connected our client-side apps to our locally-hosted servers, and then crash-learned MySQL so we could hook everything up to a database. The terminal windows multiplied like rabbits. The full stack was before us.

Every morning we do toy problems to stay algorithmically fit. A recent toy problem was called Tree Depth-First Select and I would like to show you two solutions to it in order to touch on a topic that interests me: the difference between ‘pure’ functional recursion and recursion that makes use of an inner function.

Quick primer on what a depth first search is, via Wikipedia:

Depth-first search (DFS) is an algorithm for traversing or searching tree or graph data structures. One starts at the root and explores as far as possible along each branch before backtracking.

Tree Depth-First Select asks you to —

Implement a depth-first method on a tree class.

DFSelect accepts a filter function, calls that function on each of the nodes in Depth First order, and returns a flat array of node values of the tree for which the filter returns true.

For example:

var root1 = new Tree(1);
var branch2 = root1.addChild(2);
var branch3 = root1.addChild(3);
var leaf4 = branch2.addChild(4);
var leaf5 = branch2.addChild(5);
var leaf6 = branch3.addChild(6);
var leaf7 = branch3.addChild(7);

root1.DFSelect(function (value, depth) {
  return value % 2 === 1;
}) //=> [1, 5, 3, 7]

root1.DFSelect(function (value, depth) {
  return depth === 1;
}) //=> [2, 3]

A tree has a value and children:

var Tree = function(value){
 this.value = value;
 this.children = [];
};

We are going to add our function to the Tree prototype so all instances of tree will have access to it (including all children, which are automatically created as new Trees in the addChild function [not shown for reasons of brevity]) —

Tree.prototype.DFSelect = function(filter) {
 
  // an array to hold values that pass the filter test
  truevalues = [];

var recurse = function(tree, depth){
  depth = depth || 0;
  // consider input tree’s value;
  // if (filter(tree.value, depth) would be better
  if( filter(tree.value, depth) === true ){
   //push to truenodes if filter returns true
   truevalues.push(tree.value);
  }
  for (var i = 0; i < tree.children.length; i++) {
   // set immediate children’s depth to 1.
   recurse(tree.children[i], depth+1);
  }
 };
 recurse(this);
 return truevalues;
}

This was my solution, and it is a perfect example of using a subroutine (the function called ‘recurse’) to handle the recursion. It is often more intuitive do approach recursion in this manner, because results can be held in outer variables (in this case, the array of ‘truenodes’). However, this is an example of a function producing side effects, an ‘impure’ function.

Why is that important? In many cases it may not make a huge difference, like in a toy problem solution. But toy problems are exercises, and exercising your pure functional muscles can have advantages for you as an engineer. Pure functions don’t modify any aspect of their environment outside of their own scope. Every time they execute, given the same set of inputs they will return the same result, which produces simpler, clearer, easier-to-debug code, easier-to-test code. They are the height of coding elegance.

So how can we refactor our solution to be pure? Note that we make a bit of a trade-off in terms of legibility here:

Tree.prototype.DFSelect = function(filter, depth) {

 depth = depth || 0;

 var rootSelection = filter(this.value, depth) ? [this.value] : [];

 var childSelections = this.children.map(function(child){
  return child.DFSelect(filter, depth + 1);
  });

 return [].concat.apply(rootSelection, childSelections);

};

We apply our filter to our parent node first, and use the rootSelection variable to store an array, holding either our parent node’s value, if it passes our filter, or merely an empty array, if it does not pass our filter

Next we map over our parent node’s children and recurse. On each pass of the recursion the filter will be applied to each child, which will become ‘this’; if it passes the filter, it’s value will be put in an array which will be concatenated together with all the values that pass the filter. Empty arrays produced by filter-test failures simply disappear in the concatenation.

Warning: contemplating pure functional recursion can often lead to an exploded mind.

P.S. Why use [].concat.apply instead of rootSelection.concat(childSelections)? Remember that a new rootSelection variable is being declared each time DFSelect is called. This could lead to hundreds of independent variables, each in their own scope. In order to bring this long chain of arrays together, we have to concatenate them into one array. Squint at the final return statement and you can maybe see it not as one short line of code but as a potentially very long chain of strung-together scopes, which get compressed back together when the recursion runs through the entire tree.