I guess I'm more worried about false negatives (i.e. people doing poorly who would do well on the job) than false positives. I have worked with excellent coworkers who I think would likely do really poorly on DP questions because they didn't do contest programming or didn't happen to learn it in their education.

Recursion is a great thing to include in an interview (in moderation), no objections there. Many real-world situations are naturally recursive, and a good grasp of recursion helps build a strong intuition for many aspects of programming. DP (specifically designing recursion with overlapping subproblems) is a much more specific technique that I think isn't as beneficial for programming ability, though I certainly don't doubt that people who know DP well are often also good programmers.