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.
I miss this book. Beautifully written esp. the chapter on recursion - it introduced many new types of recursion schemes than I was aware of at that time. The only book where I did almost all the exercises!
