Other commenters have already mentioned that recursion is often a more natural fit for "recursively-defined" structures like trees. Here's an example using nothing more exotic than integers.

Suppose you want to compute the greatest common divisor of two non-negative integers. There's a famous algorithm that goes all the way back to Euclid's Elements, which you can write iteratively like this:

    def gcd(a,b):
        if a<b: a,b = b,a
        while b != 0:
            a,b = b,a%b
        return a

That's pretty nice, and it's the way I would usually implement it. But in terms of readability I think the following is better:

    def gcd(a,b):
        if a<b: return gcd(b,a)
        if b==0: return a
        return gcd(b, a%b)

because it makes it explicit that the point is that at every point in the computation you're replacing gcd(a,b) with gcd(a',b') in such a way that the calculation keeps getting easier.

It turns out that if the gcd of a,b is d then there are always integers x,y such that ax+by=d, and it's sometimes useful to compute x,y along with d. (For instance: if d=1 then you have ax=1 mod b, so this gives you an efficient way of computing reciprocals in modular arithmetic.)

Here's how that goes, iteratively and then recursively. (I notice that I've used two extra state variables for the iterative version. That's what seems like the most natural approach. I'm not sure whether there's a convenient way to use only two.)

    def xgcd(a,b):
        p,q,r,s = 1,0,0,1 # a = p.a0+q.b0, b = r.a0+s.b0
        if a<b: a,b, p,q, r,s = b,a, r,s, p,q
        while b != 0:
            k = a//b
            a,b, p,q, r,s = b,a-k*b, r,s, p-k*r,q-k*s
        return a,p,q

    def xgcd(a,b):
        if a<b:
            d,x,y = xgcd(b,a)
            return d,y,x
        if b==0: return a,1,0
        k = a//b
        d,x,y = xgcd(b,a-k*b) # d = x.b + y.(a-kb)
        return d,y,x-k*y

The difference isn't dramatic in any of these cases, but I think the recursive versions are clearer because the code is closer to the underlying mathematical theorems -- e.g., gcd(a,b) = gcd(b, a mod b) -- that make it work.

[EDITED to add:] Perhaps it's useful to think of it this way. If you wanted to explain how, say, that iterative xgcd function works, you'd do it with a loop invariant; in fact, I actually wrote one, in that first comment "explaining" what p,q,r,s signify. (In real code I would be more verbose about it.) The recursive function gets the same idea across in the language itself: each iteration of the loop becomes a call to xgcd, and the loop invariant becomes the fact that the corresponding call to xgcd actually computes what it's supposed to compute.