For me, it was Touretzky's Common Lisp: A Gentle Introduction to Symbolic Computation that finally made recursion click. He gives a fantastic, simple, high-level breakdown of different recursion models with simple, non-mathematical examples. The student was ready and the master appeared.