Yes and no. The same sources of recursivity in syntax, i.e. coordination and embedding, exist in both phrase structures and dependency structures. Both broad approaches can also be formalized in a way that is mathematically rigorous. For instance, one of the earliest articles on dependency grammar, i.e. Hays 1964, demonstrated that the rewrite rules (which allow for recursivity) associated with Chomsky's first works on syntax can easily be rendered in terms of dependencies. Igor Mel'cuk, the dependency grammarian behind the grammar framework known as Meaning-Text Theory, has always emphasized the importance of mathematical stringency when producing definitions of linguistic notions. In these respects, the answer to your question is "Yes".
In another respect, though, the answer may be "No". When it comes to analyses of sentence meaning in terms of formal semantics, there is a difficulty. Most approaches to formal semantics assume an understanding of meaning compositionality in terms of syntactic structures that are strictly binary in their branching. Dependency structures are incapable of mimicking this strict binarity of branching. What this means is that dependency syntax and much of the current work on formal semantics are incompatible to an extent. As a dependency grammarian, this issue has me viewing much of the work in formal semantics with skepticism.
Putting the emphasis on formalism aside, the great advantage that dependency syntax has over phrase structure syntax is its simplicity. I can teach novice linguistics students to produce dependency analyses of basic sentences in an hour or two. The same cannot be said of students learning to produce phrase structure analyses. Consider the next two tree structures in this regard:
The dependency tree has five nodes and four edges, whereas the phrase structure tree has nine nodes and eight edges. These numbers demonstrate the minimality of dependency structures compared to the corresponding phrase structures.
I think a comment concerning the value of formalization in linguistics is also appropriate. Heavy formalisms are difficult to penetrate for most people, and they are therefore often not helpful. In fact, over-formalization can be a means of masking the fact that the linguist behind the formalisms does not have much to say that is insightful, for if they actually had something insightful to share, they would express that insight in a manner that is accessible to a wide audience.