In what scenario do you prefer recursion over a loop? Your comment made me think of code readability and maintainability. But I'm not judging. Really curious how you manage to prefer recursion over loops.

I prefer recursion to loops since loops bundle everything together in one environment; variables left over from previous iterations are still in scope, which is confusing and may cause problems, e.g. using a variable before it's been updated for this iteration, or after it's been updated for the next iteration, etc.

Recursion is just function calls. The only things which are in scope are those required by this iteration, accepted as arguments. The only thing I need to produce is a return value. This is a small, well-defined interface, as opposed to the self-interfering spaghetti code of a loop.

By accepting values as arguments and calling functions with different values, the problem of when and what to assign variables goes away; the language does it automatically by binding arguments.

Also, recursion (like function calls in general) allows thinking in terms of values, which are timeless and explicit in the code, rather than state, which is implicit and varies during execution.

Semi-related: http://chriswarbo.net/blog/2012-10-02-looping_in_javascript....

Anecdote: After 12 hours of programming, I still had to implement some easy string search. I could not think straight at that stage and several imperative solutions failed. Then I thought "dammit, let's use a functional approach with recursion". It was faster to write, tail recursive, and correct the first time.

Which environment are you working in that doesn't have a string search as part of the standard library?

INTERCAL. Seriously, what does it have to do with the point I made?

If working with trees, recursion is usually easier to understand.

If working with recursively expressed data, recursively expressed algorithms are usually easier to understand.

My 2c: Building a hierarchical structure requiring opening and closing tags/code/etc (like HTML) is where I like to use recursion. The code structure matches the data structure, so you only have to reason about it once.

I think it's rather universal that, for instance, a depth-first tree traversal is best done recursively.

In my experience, I almost always prefer recursion since it allows me to work more closely with the structure of the original data that I'm interested in instead of a set of a proxy indices which I have to track separately.

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.

Nice. Here's an Erlang version of your code, which I think reads even more like math:

  gcd(A, B) when B == 0 -> A;
  gcd(A, B) when A < B  -> gcd(B, A);
  gcd(A, B)             -> gcd(B, A rem B).

I also really appreciated the posting of more of Dijkstra's thoughts (from rer0tsaz) above, in particular this line struck a chord:

  When programming languages emerged, the "dynamic" nature of
  the assignment statement did not seem to fit too well into the
  "static" nature of traditional mathematics.
  

(Along those lines, Erlang's recasting of the equals sign as a pattern matching operator felt so natural when I learned how it worked.)

[Edit: zap redundant sentence.]

That syntax definitely helps. It is readable even though the variable names are non-descriptive.