There's nothing wrong with using recursion in Clojure. Use loop + recur, it works fine 99% of the time. I very rarely find myself using loop + recur though; they are more low-level than you usually need. map, reduce, filter, for (list comprehensions) and friends are better.
Stateful iteration in Clojure doesn't make sense because the data structures you're (usually) working with are immutable. You should instead be taking some structure and producing a new structure based on it (which is why map and friends fit well). The immutable data structures are the main place you have to change your thinking in my opinion; once you get used to those, everything else clicks into place.
Laziness can be safely ignored or taken for granted most of the time (but keep in mind that it's going on, so you know when to force evaluation via dorun/doall for example). The Programming Clojure book does go a lot into lazy sequences but I think they only really make sense for certain kinds of problems, e.g. dealing with infinite lists and such.
Having written a web app in Clojure and Common Lisp, I personally prefer Clojure, but both work fine. Compojure