# Dependency resolution and mutual recursion

Recursion can be tricky to get your mind around, but satisfying once you do. I recently stumbled upon a problem for which a kind of *mutual* recursion turned out to be the simplest solution. It took me a moment to figure out (because I found it even more brain-bendy than "normal" recursion), but I was glad once I did. I hope you enjoy it as much as I do.

## The (simpler) problem

Let's start with a simple version of the problem, for which (normal) recursion is sufficient.

Suppose we're trying to write a dependency resolution algorithm. My package (or more generally, *artifact*) depends on specific versions of some others — which, in turn, depend on others, etc. We want to collect the set of ALL transitive dependenices (the "transitive closure").

A simple way to do this is with a depth-first traversal. The skeleton would look like this:

def resolve(Artifact a): Set[Artifact] {
  Set deps  // Collect all deps here
  for (dep in a.deps) {
    deps += resolve(dep)
  }
  return deps
}

Of course, this doesn't handle error cases. For example, we should fail if there's a conflict (e.g., I depend on Foo 1.1, but I also depend on something else that requires Foo 1.2). We can accomplish that by keeping track of accumulated dependencies instead of returning it as a set:

def resolve(Artifact a, Set[Artifact] acc) {
  if (a.name in acc and a.version doesn't match)
    throw DependencyResolutionError
  else
    acc += a
  
  for (dep in a.deps) {
    resolve(dep, acc)
  }
}

We can also add a helper method for the user:

def resolve(Artifact a): Set[Artifact] {
  Set acc = Set.empty
  resolve(a, acc)
  return acc
}

## The (more fun) problem

In the simple version, we depend on only one version of each artifact. But what if multiple versions are allowed? E.g., what if I can depend on `Foo 1.x`?

Suppose my artifact has three dependencies: `Foo 1.x`, `Bar 1.x`, `Baz 1.x`. And suppose there are three such version of `Foo`, four of `Bar`, and five of `Baz`. Then I potentially have to try 3 * 4 * 5 = 60 combinations to see if there's a good completion.

One way to do this would be to iterate over all 60 such tuples (x, y, z) and do a depth-first traversal for each. It may be tempting to try it like this:

def resolve(Artifact a, Set[Artifact] acc) {
  if (a.name in acc and a.version doesn't match)
    throw DependencyResolutionError
  else
    acc += a
    
  // Generate all tuples ((x1, y1, z1), (x1, y1, z2), ...)
  // Perhaps do it in a lazy way, to save time and space.
  List[List[Artifacts]] depsList = ...
  
  for (deps in depsList) {
    for (dep in deps) {
      resolve(dep, acc)
    }
  }
}

But this gets ugly quickly. Not only do we need to catch exceptions, but we need to unwind `acc` to recover from those failed searches. Moreover, we shouldn't just blindly continue down the list of tuples. If resolution of `x1` throws while resolving `(x1, y1, z1)`, we shouldn't continue trying `(x1, y1, z2)` etc. We need something smarter.

An alternative is to use recursion again. Instead of explicitly enumerating all tuples, we call a function to handle (all possible choices for) the first element of the tuple, and it is responsible for invoking the function on the second element, etc.

def resolve(a: Artifact, acc: Set[Artifact]): Set[Artifact] {
  if (a.name in acc and a.version doesn't match)
    throw DependencyResolutionError
  else
    acc += a

 return a + walkChildren(a.deps, 0, acc + a)
}

def walkChildren(children: List[List[Artifact]], i: Int, acc: Set[Artifact]): Set[Artifact] {
  if (i >= children.length) return Set.empty

  for (child in children[i]) {
    res = resolve(child, acc)
    return res + walkChildren(children, i+1, acc + res)
  }
}