I come from a physics background, and thus, lots of maths. I find easy to spot problems well suited to recursive/dynamic programming solutions by finding similarities with proof by induction.
In proof by induction you have two parts:
- you prove that if something is true for iteration N, it is also true for iteration N+1
- you prove that it is true for iteration 1
In recursive programming/dynamic programming:
- you identify an exit condition (for example, you hard wire the solution for iteration 1)
- you calculate solution for iteration N given the solution for iteration N-1
So, as others answered, it is a matter of experience and picking the hints, but you can re-use other skills to guide you. After that, you need to always have the two parts which I mentioned: if you don't, then it won't work.
For example, to generate all the permutations of a set:
- exit condition: if you only have one element, return it
- recursion: the permutations of a set of N items are the N sets of permutations you get by choosing each element and combining the with all the N-1 sets of (many) permutations of the subset you get by removing the element.