To understand recursion get "The Little Lisper" or the later book "The Little Schemer". To know when not to use recursion and use iteration instead, look at "Algorithms + Data Structures = Programs" and finally, you can delve into the mathematics of primitive and non-primitive recursive function with "Recursive Functions in Computer Theory".

Good reading to all.