No testing whatsoever is going to be able to be sufficient in this case, not even tons of real world data or fuzzing. A 100% code coverage, or even 100% path coverage is insufficient to test recursive functions.

Either the recursive function stands up to a formal proof (shouldn't be that difficult in this case), or it doesn't. If the code is too intertwined with application specific code to rule out side effects, that's where to start.

The algorithm itself sounds like a simple flooding algorithm, similar to a simple broad first search, with the addition of a blacklist which must not intersect with the list of visited nodes, run from all nodes.


    foreach nodes as node
        foreach nodes as tmp
            tmp.status = unmarked

        tovisit = []
        tovisit.push(node)
        node.status = required

        while |tovisit| > 0 do
            next = tovisit.pop()
            foreach next.requires as requirement
                if requirement.status = unmarked
                    tovisit.push(requirement)
                    requirement.status = required
                else if requirement.status = blacklisted
                    return false
            foreach next.collides as collision
                if collision.status = unmarked
                    requirement.status = blacklisted
                else if requirement.status = required
                    return false
    return true

This iterative algorithm fulfills the condition that no dependency may be required and blacklisted at the same time, for graphs of arbitrary structure, starting from any arbitrary artifact whereby the starting artifact is always required.

While it may or may not be as fast as your own implementation, it can be proven that it terminates for all cases (as for each iteration of the outer loop each element can only be pushed once onto the `tovisit` queue), it floods the entire reachable graph (inductive proof), and it detects all cases where an artifact is required to be required and blacklisted simultaneously, starting from each node.

If you can show that your own implementation has the same characteristics, you can prove correctness without resulting to unit testing. Only the basic methods for pushing and popping from queues, counting queue length, iterating over properties and alike need to be tested and shown to be free of side effects.

**EDIT:** What this algorithm does not prove, is your graph being free of cycles. [Directed acyclic graphs](https://en.wikipedia.org/wiki/Directed_acyclic_graph) are a well researched topic though, so finding a ready made algorithm to prove this property should be easy as well.

As you can see, there is no need to reinvent the wheel, at all.