Of all the ways to shoot yourself in the foot with C, recursive mutexes seem relatively benign. The implementation is a handful of lines of code, and they're not always a symptom of bad design, either; imagine needing to lock each node in a path through a (possibly cyclic) graph.

If two different threads were trying to lock different paths that entered the same cycle at different nodes, there can be a deadlock.

  X -> B
  B -> C
  C -> B
  Y -> C

Thread 1 tries to lock X B C; thread 2 tries to lock Y C B; deadlock with 1 holding X and B, 2 holding Y and C.

It's possible that your paths may be more restricted than this, but I reckon keeping the paths and cycles clean would be a bigger problem than recursive mutexes.

Recursive mutexes are useful when you need to implement multithreading a posteriori and cannot evaluate all the locking paths.

When adding locking without evaluating all locking paths, how can you be sure none of those paths cause a deadlock ?

You cannot self deadlock with a a single recursive mutex.