It Is What It Is (And Nothing Else) – Why Recursion Still Matters

So there are holy wars to be expected.

I think you point out something really interesting with this notion of formal/informal. I think it's tough to draw that line because a lot of "formal" reasoning is designed to be informally used but needs formality in its presentation.

Or, to be more concrete, I think that most programmers use a slew of semi-actualized denotations when understanding code. Usually this is a transparent process and a skill gained by experienced programmers is to align your semi-actualized denotations so that they both agree with one another and with reality.

Formalism is just a tool to get ahold of these and fully actualize them. It's something one could choose to invest in—or not.

But the underlying process of transporting understanding and using the best denotation for the moment is very real regardless of the level of formality.

In my mind recursion is a snake that has eaten a smaller snake, whereas an sram cell is a snake eating its own tail.

   Continuations are easy: functions are hard.

Computer Science is it's own, highly diverse field, composed of software engineering, algorithms, theory of computation, human-computer-interaction, AI, systems engineering, databases, security, graphics, scientific computing, and many other sub-divisions.

CS hasn't been solely a branch of mathematics for decades.

See what Stanford considers part of CS: http://www-cs.stanford.edu/research

See what Berkeley considers part of EECS: http://www.eecs.berkeley.edu/Research/Areas/

It is up to you to choose which lectures you want to use your optional credits for.

> 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. For lack of an adequate theory mathematicians did not feel to easy about it, and, because it is the repetitive construct that creates the need for assignment to variables, mathematicians did not feel to easy about repetition either. When programming languages without assignments and without repetition --such as pure LISP-- were developed many felt greatly relieved. They were back on familiar grounds and saw a glimmer of hope of making programming an activity with a firm and respectable mathematical basis. (Up to this very day there is among the more theoretically inclined computing scientists still a widespread feeling that recursive programs "come more naturally" than repetitive ones.)

Continued https://tinyletter.com/programmingphilosophy/letters/i-don-t...

True.

> ... hence are of equal complexity in terms of reasoning.

False. That's like saying that Stokes' Theorem says that the integral of a differential form over the boundary of a manifold is equal to the integral of it's derivative over the whole manifold, and therefore the two integrals are equally easy to do. In fact, the two integrals are often not equally easy to do, which is the primary practical reason that we care about Stokes' Theorem - it gives us a way to convert hard integrals into easier ones.

You cannot use formal equivalence to prove practical ease of doing the problem.

But the situation isn't even that simple. A blanket statement that "loops are much easier to analyze and reason about" is also false. It depends on the situation, and often on who's doing the reasoning. Different people think in different ways.

My apologies for making an absolute statement with unclear terms, thus inviting uncharitable interpretations.

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....

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.

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

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

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

[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.