newtons method of square root approximation was originally an iterative algorithm.
The iterative versions of a recursive solution are slightly slower but less memory intensive, and additionally a major PITA to code at all. a recursive solution is a lot easier to understand and read.
And then you get messy stuff like mutual recursion between four or five class modules- or recursion within them... for example, my expression evaluation library has a "CParser" main object. the stack item for a function has an array of other CParser objects that represent each argument. It would be extremely difficult to make a "iterative" type of solution for this, so really I found an exception myself.
I guess it depends on the complexity of the algorithm more then the complexity of the recursion used to implement it.