Other commenters have already mentioned that recursion is often a more natural fit for &quot;recursively-defined&quot; structures like trees. Here&#x27;s an example using nothing more exotic than integers.<p>Suppose you want to compute the greatest common divisor of two non-negative integers. There&#x27;s a famous algorithm that goes all the way back to Euclid&#x27;s <i>Elements</i>, which you can write iteratively like this:<p><pre><code>    def gcd(a,b):
        if a&lt;b: a,b = b,a
        while b != 0:
            a,b = b,a%b
        return a
</code></pre>
That&#x27;s pretty nice, and it&#x27;s the way I would usually implement it. But in terms of <i>readability</i> I think the following is better:<p><pre><code>    def gcd(a,b):
        if a&lt;b: return gcd(b,a)
        if b==0: return a
        return gcd(b, a%b)
</code></pre>
because it makes it explicit that the point is that at every point in the computation you&#x27;re replacing gcd(a,b) with gcd(a&#x27;,b&#x27;) in such a way that the calculation keeps getting easier.<p>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&#x27;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.)<p>Here&#x27;s how that goes, iteratively and then recursively. (I notice that I&#x27;ve used two extra state variables for the iterative version. That&#x27;s what seems like the most natural approach. I&#x27;m not sure whether there&#x27;s a convenient way to use only two.)<p><pre><code>    def xgcd(a,b):
        p,q,r,s = 1,0,0,1 # a = p.a0+q.b0, b = r.a0+s.b0
        if a&lt;b: a,b, p,q, r,s = b,a, r,s, p,q
        while b != 0:
            k = a&#x2F;&#x2F;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&lt;b:
            d,x,y = xgcd(b,a)
            return d,y,x
        if b==0: return a,1,0
        k = a&#x2F;&#x2F;b
        d,x,y = xgcd(b,a-k*b) # d = x.b + y.(a-kb)
        return d,y,x-k*y
</code></pre>
The difference isn&#x27;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.<p>[EDITED to add:] Perhaps it&#x27;s useful to think of it this way. If you wanted to explain how, say, that iterative xgcd function works, you&#x27;d do it with a loop invariant; in fact, I actually wrote one, in that first comment &quot;explaining&quot; 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&#x27;s supposed to compute.