Much mathematics is intimately tied to recursion, be it in definitions (like factorials and integer powers) and proofs by induction. This is also very relevant in computer science and programming. However, it is my experience that students have a hard time to understand what is going on, and even more to see where and how to apply the techniques. My impression is that by now, through decades of daily use, I'm not able anymore to see where the student's dificulties are. When presented with a problem asking for a induction proof, most are able to write down a reasonable answer, but is seems they still feel unconfortable with it. Unless specifically directed to use it, they will very rarely explore it's applicability.
Are there any suggestions on what to emphasize, what symptoms alert of particular types of misunderstandings?