Call graphs are the most familiar of software's many graphs. Here, nodes represent functions and edges represent calls between those functions. At this level of analysis, we don't care which line of function A calls function B; that's abstracted away. We only care that the call happens somewhere inside of A.

As an example, Underscore.js defines its first function as shown below. (If the details of these functions' internals aren't interesting, skipping them is OK.) We're concerned only with the structural relationships here.)

_.first = function(array, n, guard) {
  if (array == null) return void 0;
  if (n == null || guard) return array[0];
  return _.initial(array, array.length - n);
};

This references the function initial, which returns a list with the last n elements removed.

_.initial = function(array, n, guard) {
  return slice.call(array, 0, Math.max(0, array.length - (n == null || guard ? 1 : n)));
};

initial in turn references slice and Math.max. We can visualize this small piece of underscore as a call graph:

This graph is acyclic: we can't start at a node, follow a series of edges, and end up back at the node that we started at. Acyclic call graphs are desirable because they let us put function calls in a sensible order. For example, in this example we can think of first as the entry point; it sets off the series of calls to other functions. We can abstract those details away if we like, thinking of first as a black box, ignoring its call to initial which calls yet more functions.

Things are more difficult when we consider call graph cycles, which correspond to recursive function calls. For example, the recursive factorial function calls itself:

function fact(n) {
  if (n == 0) {
    return 1;
  } else {
    return n * fact(n - 1);
  }
}

Its call graph is the smallest possible cyclic graph. We can begin at fact, follow the only available edge, and end up back at fact, forming a cycle:

Cyclic call graphs become confusing quickly, mirroring the confusion of recursion in general. With many calls between the beginning and end of the recursive call relationship, we might not even notice the recursion. In this example, we may miss the recursion until we examine all of g, h, i, and j, which calls back to g.

This is why recursion involving multiple functions is confusing: the recursion is only visible after we trace through several calls. Our graph diagram above shows the recursion clearly, but that same recursion is invisible when looking at any given function in the code.