Another suitable problem solved by recursion in an elegant way is the task of walking the nodes in a graph-like data structure. If I wanted to create a library for navigating a graph-like structure, then I would be hard pressed to find a solution more elegant than a recursive one. A graph that I find particularly interesting is a (partial) graph of the programming languages that have influenced JavaScript either directly or indirectly.

Figure 6-4. A partial graph of programming language influences

I could use a class-based or object-based representation, where each language and connection is represented by objects of type Node and Arc, but I think I’d prefer to start with something simple, like an array of arrays of strings:

var influences = [
  ['Lisp', 'Smalltalk'],
  ['Lisp', 'Scheme'],
  ['Smalltalk', 'Self'],
  ['Scheme', 'JavaScript'],
  ['Scheme', 'Lua'],
  ['Self', 'Lua'],
  ['Self', 'JavaScript']];

Each nested array in influences represents a connection of “influencer” to “influenced” (e.g., Lisp influenced Smalltalk) and encodes the graph shown in Figure 6-4. A recursive function, nexts, is defined recursively as follows(Paulson 1996):

function nexts(graph, node) {
  if (_.isEmpty(graph)) return [];

  var pair = _.first(graph);
  var from = _.first(pair);
  var to   = second(pair);
  var more = _.rest(graph);

  if (_.isEqual(node, from))
    return construct(to, nexts(more, node));
  else
    return nexts(more, node);
}

The function nexts walks the graph recursively and builds an array of programming languages influenced by the given node, as shown here:

nexts(influences, 'Lisp');
//=> ["Smalltalk", "Scheme"]

The recursive call within nexts is quite different than what you’ve seen so far; there’s a recursive call in both branches of the if statement. The “then” branch of nexts deals directly with the target node in question, while the else branch ignores unimportant nodes.

It would take very little work to make nexts take and traverse multiple nodes, but I leave that as an exercise to the reader. Instead, I’ll now cover a specific type of graph-traversal recursive algorithm called depth-first search.

In this section I’ll talk briefly about graph searching and provide an implementation of a depth-first search function. In functional programming, you’ll often need to search a data structure for a piece of data. In the case of hierarchical graph-like data (like influences), the search solution is naturally a recursive one. However, to find any given node in a graph, you’ll need to (potentially) visit every node in the graph to see if it’s the one you’re looking for. One node traversal strategy called depth-first visits every leftmost node in a graph before visiting every rightmost node (as shown in Figure 6-5).

Figure 6-5. Traversing the influences graph depth-first

Unlike the previous recursive implementations, a new function depthSearch should maintain a memory of nodes that it’s already seen. The reason, of course, is that another graph might have cycles in it, so without memory, a “forgetful” search will loop until JavaScript blows up. However, because a self-recursive call can only interact from one invocation to another via arguments, the memory needs to be sent from one call to the next via an “accumulator.” An accumulator argument is a common technique in recursion for communicating information from one recursive call to the next. Using an accumulator, the implementation of depthSearch is as follows:

function depthSearch(graph, nodes, seen) {
  if (_.isEmpty(nodes)) return rev(seen);

  var node = _.first(nodes);
  var more = _.rest(nodes);

  if (_.contains(seen, node))
    return depthSearch(graph, more, seen);
  else
    return depthSearch(graph,
                       cat(nexts(graph, node), more),
                       construct(node, seen));
}

As you’ll notice, the third parameter, seen, is used to hold the accumulation of seen nodes to avoid revisiting old nodes and their children. A usage example of depthSearch is as follows:

depthSearch(influences, ['Lisp'], []);
//=> ["Lisp", "Smalltalk", "Self", "Lua", "JavaScript", "Scheme"]

depthSearch(influences, ['Smalltalk', 'Self'], []);
//=> ["Smalltalk", "Self", "Lua", "JavaScript"]

depthSearch(construct(['Lua','Io'], influences), ['Lisp'], []);
//=> ["Lisp", "Smalltalk", "Self", "Lua", "Io", "JavaScript", "Scheme"]

You may have noticed that the depthSearch function doesn’t actually do anything. Instead, it just builds an array of the nodes that it would do something to (if it did anything) in depth-first order. That’s OK because later I’ll re-implement a depth-first strategy using functional composition and mutual recursion. First, let me take a moment to talk about “tail calls.”

function tcLength(ary, n) {
  var l = n ? n : 0;

  if (_.isEmpty(ary))
    return l;
  else
    return tcLength(_.rest(ary), l + 1);
}

tcLength(_.range(10));
//=> 10

Throughout this book, I’ve implemented some common function composition functions—curry1, partial, and compose—but I didn’t describe how to create your own. Fortunately, the need to create composition functions is rare, as much of the composition capabilities needed are provided by Underscore or are implemented herein. However, in this section, I’ll describe the creation of two new combinators, orify and andify, implemented using recursion.

Recall that I created a checker function way back in Chapter 4 that took some number of predicates and returned a function that determined if they all returned truthiness for every argument supplied. I can implement the spirit of checker as a recursive function called andify:^[67]

function andify(/* preds */) {
  var preds = _.toArray(arguments);

  return function(/* args */) {
    var args = _.toArray(arguments);

    var everything = function(ps, truth) {
      if (_.isEmpty(ps))
        return truth;
      else
        return _.every(args, _.first(ps))
               && everything(_.rest(ps), truth);
    };

    return everything(preds, true);
  };
}

Take note of the recursive call in the function returned by andify, as it’s particularly interesting. Because the logical and operator, &&, is “lazy,” the recursive call will never happen should the _.every test fail. This type of laziness is called “short-circuiting,” and it is useful for avoiding uneccessary computations. Note that I use a local function, everything, to consume the predicates given in the original call to andify. Using a nested function is a common way to hide accumulators in recursive calls.

Observe the action of andify here:

var evenNums = andify(_.isNumber, isEven);

evenNums(1,2);
//=> false

evenNums(2,4,6,8);
//=> true

evenNums(2,4,6,8,9);
//=> false

The implementation of orify is almost exactly like the form of andify, except for some logic reversals:^[68]

function orify(/* preds */) {
  var preds = _.toArray(arguments);

  return function(/* args */) {
    var args = _.toArray(arguments);

    var something = function(ps, truth) {
      if (_.isEmpty(ps))
        return truth;
      else
        return _.some(args, _.first(ps))
               || something(_.rest(ps), truth);
    };

    return something(preds, false);
  };
}

Like andify, should the _.some function ever succeed, the function returned by orify short-circuits (i.e., any of the arguments match any of the predicates). Observe:

var zeroOrOdd = orify(isOdd, zero);

zeroOrOdd();
//=> false

zeroOrOdd(0,2,4,6);
//=> true

zeroOrOdd(2,4,6);
//=> false

This ends my discussion of self-recursive functions, but I’m not done with recursion quite yet. There is another way to achieve recursion and it has a catchy name: mutual recursion.

Another example where recursion seems like a good fit is to implement a function to “deep” clone an object. Underscore has a _.clone function, but it’s “shallow” (i.e., it only copies the objects at the first level):

var x = [{a: [1, 2, 3], b: 42}, {c: {d: []}}];

var y = _.clone(x);

y;
//=> [{a: [1, 2, 3], b: 42}, {c: {d: []}}];

x[1]['c']['d'] = 1000000;

y;
//=> [{a: [1, 2, 3], b: 42}, {c: {d: 1000000}}];

While in many cases, _.clone will be useful, there are times when you’ll really want to clone an object and all of its subobjects.^[70] Recursion is a perfect task for this because it allows us to walk every object in a nested fashion, copying along the way. A recursive implementation of deepClone, while not robust enough for production use, is shown here:

function deepClone(obj) {
  if (!existy(obj) || !_.isObject(obj))
    return obj;

  var temp = new obj.constructor();
  for (var key in obj)
    if (obj.hasOwnProperty(key))
      temp[key] = deepClone(obj[key]);

  return temp;
}

When deepClone encounters a primitive like a number, it simply returns it. However, when it encounters an object, it treats it like an associative structure (hooray for generic data representations) and recursively copies all of its key/value mappings. I chose to use the obj.hasOwnProperty(key) to ensure that I do not copy fields from the prototype. I tend to use objects as associative data structures (i.e., maps) and avoid putting data onto the prototype unless I must. The use of deepClone is as follows:

var x = [{a: [1, 2, 3], b: 42}, {c: {d: []}}];

var y = deepClone(x);

_.isEqual(x, y);
//=> true

y[1]['c']['d'] = 42;

_.isEqual(x, y);
//=> false

The implementation of deepClone isn’t terribly interesting except for the fact that JavaScript’s everything-is-an-object foundation really allows the recursive solution to be compact and elegant. In the next section, I’ll re-implement depthSearch using mutual recursion, but one that actually does something.

Walking nested objects like in deepClone is nice, but not frequently needed. Instead, a far more common occurrence is the need to traverse an array of nested arrays. Very often you’ll see the following pattern:

doSomethingWithResult(_.map(someArray, someFun));

The result of the call to _.map is then passed to another function for further processing. This is common enough to warrant its own abstraction, I’ll call it visit, implemented here:

function visit(mapFun, resultFun, array) {
  if (_.isArray(array))
    return resultFun(_.map(array, mapFun));
  else
    return resultFun(array);
}

The function visit takes two functions in addition to an array to process. The mapFun argument is called on each element in the array, and the resulting array is passed to resultFun for final processing. If the thing passed in array is not an array, then I just run the resultFun on it. Implementing functions like this is extremely useful in light of partial application because one or two functions can be partially applied to form a plethora of additional behaviors from visit. For now, just observe how visit is used:

visit(_.identity, _.isNumber, 42);
//=> true

visit(_.isNumber, _.identity, [1, 2, null, 3]);
//=> [true, true, false, true]

visit(function(n) { return n*2 }, rev, _.range(10));
//=> [18, 16, 14, 12, 10, 8, 6, 4, 2, 0]

Using the same principle behind flat, I can use visit to implement a mutually recursive version of depthSearch called postDepth:^[71]

function postDepth(fun, ary) {
  return visit(partial1(postDepth, fun), fun, ary);
}

The reason for the name postDepth is that the function performs a depth-first traversal of any array performing the mapFun on each element after expanding its children. A related function, preDepth, performs the mapFun call before expanding an element’s children and is implemented as follows:

function preDepth(fun, ary) {
  return visit(partial1(preDepth, fun), fun, fun(ary));
}

There’s plenty of fun to go around in the case of pre-order depth-first search, but the principle is sound; just perform the function call before moving onto the other elements in the array. Let’s see postDepth in action:

postDepth(_.identity, influences);
//=> [['Lisp','Smalltalk'], ['Lisp','Scheme'], ...

Passing the _.identity function to the *Depth functions returns a copy of the influences array. The execution scheme of the mutually recursive functions evenSteven, oddJohn, postDepth and visit is itself a graph-like model, as shown in Figure 6-6.

Figure 6-6. Mutually recursive functions execute in a graph-like way

What if I want to capitalize every instance of Lisp? There’s a function to do that:

postDepth(function(x) {
  if (x === "Lisp")
    return "LISP";
  else
    return x;
}, influences);

//=> [['LISP','Smalltalk'], ['LISP','Scheme'], ...

So the rule is that if I want to change a node, then I do something with it and return the new value; otherwise, I just return the node. Of course, the original array is never modified:

influences;
//=> [['Lisp','Smalltalk'], ['Lisp','Scheme'], ...

What if I want to build an array of all of the languages that another language has influenced? I could perform this act as follows:

function influencedWithStrategy(strategy, lang, graph) {
  var results = [];

  strategy(function(x) {
    if (_.isArray(x) && _.first(x) === lang)
      results.push(second(x));

    return x;
  }, graph);

  return results;
}

The function influencedWithStrategy takes one of the depth-first searching functions and walks the graph, building an array of influenced languages along the way:

influencedWithStrategy(postDepth, "Lisp", influences);
//=> ["Smalltalk", "Scheme"]

Again, while I mutated an array to build the results, the action was confined to the internals of the influencedWithStrategy function localizing its effects.

Extrapolating from the nature of a trampoline, I’ll end this section by showing a couple of examples of the infinite. Using recursion, I can demonstrate how to build and process infinite streams of “lazy” data, and likewise call mutual functions until the heat death of the sun. By lazy, I only mean that portions of a structure are not calculated until needed. By contrast, consider the use of the cycle function defined earlier in this chapter:

_.take(cycle(20, [1,2,3]), 11);
//=> [1, 2, 3, 1, 2, 3, 1, 2, 3, 1, 2]

In this call, the array created by cycle is definitely not lazy, because it is fully constructed before being passed to _.take. Even though _.take only needed 11 elements from the cycled array, a full 60 elements were generated. This is quite inefficient, but alas, the default in Underscore and JavaScript itself.

However, a basic (and some would say base) way to view an array is that it consists of the first cell followed by the rest of the cells. The fact that Underscore provides a _.first and _.rest hints at this view. An infinite array can likewise be viewed as a “first” or “head,” and a “rest” or “tail.” However, unlike a finite array, the tail of an infinite array may or may not yet exist. Breaking out the head and tail view into an object might help to conceptualize this view (Houser 2013):

{head: aValue, tail: ???}

The question arises: what should go into the tail position of the object? The simple answer, taken from what was shown in oddOline, is that a function that calculates the tail is the tail. Not only is the tail a normal function, it’s a recursive function.

The head/tail object requires some maintenance, and is built using two functions: (1) a function to calculate the value at the current cell, and (2) another function to calculate the “seed” value for the next cell. In fact, the type of structure built in this way is a weak form of what is known as a generator, or a function that returns each subsequent value on demand. Keeping all of this in mind, the implementation of generator is as follows:^[72]

function generator(seed, current, step) {
  return {
    head: current(seed),
    tail: function() {
      console.log("forced");
      return generator(step(seed), current, step);
    }
  };
}

As shown, the current parameter is a function used to calculate the value at the head position and step is used to feed a value to the recursive call. The key point about the tail value is that it’s wrapped in a function and not “realized” until called. I can implement a couple of utility functions useful for navigating a generator:

function genHead(gen) { return gen.head }
function genTail(gen) { return gen.tail() }

The genHead and genTail functions do exactly what you think—they return the head and tail. However, the tail return is “forced.” Allow me to create a generator before demonstrating its use:

var ints = generator(0, _.identity, function(n) { return n+1 });

Using the generator function, I can define the full range of integers. Now, using the accessor functions, I can start plucking away at the front:

genHead(ints);
//=> 0

genTail(ints);
// (console) forced
//=> {head: 1, tail: function}

The call to genHead did not force the tail of ints, but a call to genTail did, as you might have expected. Executing nested calls to genTail will likewise force the generator to a depth equal to the number of calls:

genTail(genTail(ints));
// (console) forced
// (console) forced
//=> {head: 2, tail: function}

This is not terribly exciting, but using just these two functions I can build a more powerful accessor function like genTake, which builds an array out of the first n entries in the generator:

function genTake(n, gen) {
  var doTake = function(x, g, ret) {
    if (x === 0)
      return ret;
    else
      return partial(doTake, x-1, genTail(g), cat(ret, genHead(g)));
  };

  return trampoline(doTake, n, gen, []);
}

As shown, genTake is implemented using a trampoline, simply because it makes little sense to provide a function to traverse an infinite structure that explodes with a “Too much recursion” error for an unrelated reason. Using genTake is shown here:

genTake(10, ints);
// (console) forced x 10
//=> [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

genTake(100, ints);
// (console) forced x 100
//=> [0, 1, 2, 3, 4, 5, 6, ..., 98, 99]

genTake(1000, ints);
// (console) forced x 1000
//=> Array[1000]

genTake(10000, ints);
// (console) forced x 10000
// wait a second
//=> Array[10000]

genTake(100000, ints);
// (console) forced x 100000
// wait a minute
//=> Array[100000]

genTake(1000000, ints);
// (console) forced x 1000000
// wait an hour
//=> Array[1000000]

While not necessarily the fastest puppy in the litter, it’s interesting to see how the “trampoline principle” works to define structures of infinite size, without blowing the stack, and while calculating values on demand. There is one fatal flaw with generators created with generator: while the tail cells are not calculated until accessed, they are calculated every time they are accessed:

genTake(10, ints);
// (console) forced x 10
//=> [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

Knowing that I already called genTake to calculate the first 10 entries, it would have been nice to avoid performing the same actions again, but building a full-fledged generator is outside the scope of this book.^[73]

Of course there is no free lunch, even when using trampolines. While I’ve managed to avoid exploding the call stack, I’ve just transferred the problem to the heap. Fortunately, the heap is orders of magnitude larger than the JavaScript call stack, so you’re far less likely to run into a problem of memory consumption when using a trampoline.

Aside from the direct use of a trampoline, the idea of “trampolineness” is a general principle worth noting in JavaScript seen in the wild—something I’ll discuss presently.

Asynchronous JavaScript APIs—like setTimeout and the XMLHttpRequest library (and those built on it like jQuery’s $.ajax)—have an interesting property relevant to the discussion of recursion. You see, asynchronous libraries work off of an event loop that is non-blocking. That is, if you use an asynchronous API to schedule a function that might take a long time, then the browser or runtime will not block waiting for it to finish. Instead, each asynchronous API takes one or more “callbacks” (just functions or closures) that are invoked when the task is complete. This allows you to perform (effectively) concurrent tasks, some immediate and some long-running, without blocking the operation of your application.^[74]

An interesting feature of non-blocking APIs is that calls return immediately, before any of the callbacks are ever called. Instead, those callbacks occur in the not-too-distant future:^[75]

setTimeout(function() { console.log("hi") }, 2000);
//=> returns some value right away
// ... about 2 seconds later
// hi

A truly interesting aspect of the immediate return is that JavaScript cleans up the call stack on every new tick of the event loop. Because the asynchronous callbacks are always called on a new tick of the event loop, even recursive functions operate with a clean slate! Observe the following:

function asyncGetAny(interval, urls, onsuccess, onfailure) {
  var n = urls.length;

  var looper = function(i) {
    setTimeout(function() {
      if (i >= n) {
        onfailure("failed");
        return;
      }

      $.get(urls[i], onsuccess)
        .always(function() { console.log("try: " + urls[i]) })
        .fail(function() {
          looper(i + 1);
        });
    }, interval);
  }

  looper(0);
  return "go";
}

You’ll notice that when the call to jQuery’s asynchronous $.get function fails, a recursive call to looper is made. This call is no different (in principle) than any other mutually recursive call, except that each invocation occurs on a different event-loop tick and starts with a clean stack. For the sake of completeness, the use of asyncGetAny is as follows:^[76]

var urls = ['http://dsfgfgs.com', 'http://sghjgsj.biz', '_.html', 'foo.txt'];

asyncGetAny(2000,
  urls,
  function(data) { alert("Got some data") },
  function(data) { console.log("all failed") });
//=> "go"

// (console after 2 seconds) try: http://dsfgfgs.com
// (console after 2 seconds) try: http://sghjgsj.biz
// (console after 2 seconds) try: _.html

// an alert box pops up with 'Got some data' (on my computer)

There are better resources for describing asynchronous programming in JavaScript than this book, but I thought it worth mentioning the unique properties of the event loop and recursion. While tricky in practice, using the event loop for maximum benefit can make for highly efficient JavaScript applications.