Graph problems would be hard without recursion I think. I've been working on some problems that are naturally expressed as graphs, and recursion is the natural way to do some things; it's be quite hard to do some things I did iteratively, now that I think about it (that is, without 'emulating' recursion with an 'explicit', manually-maintained stack).
Yes. Though breadth-first approaches look much more imperative than depth-first traversals. That's because basically you exchange the stack for a queue. (Those algorithms can still look nice in, say, Haskell.)
