As a general response, it was my conclusion that a recursive approach is most importantly the safest approach, and also a clean one. Perhaps improved documentation would help make things more clear. The overall solution is rather complex, but it's a complex problem to solve. None the less, I tried to solve it with manageable pieces that should do simple things.

1) I copy a specific set of units
2) I find their direct dependencies, determine which are available that I don't already have, and call step 1 with the result

This saves us from having to generate an entire dependency graph at once, guards against circular deps, etc. Trying to do this without the duplication you mention would be much more complex and tricky, so I think this is a simple solution that still performs well.