Wouldn't that be enough reason? They're supposed to teach you how to write good code, and that includes readable code.
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.
On the other hand, I studied CS in South America, and I can count on one hand the lectures which aimed to teach you "how to write good code". Maybe one or two of them, and only in the macro "good software engineering practices" sense. Most of the others assumed you sort of picked up how to code on your own, or that you asked other students or TAs on the side. There absolutely were NO "how to code" lectures, and the overall idea you got was that CS was a theory-heavy degree. Recursion, proofs, type theory, graph theory, etc, were absolutely the focus of the degree.
There was a different degree called "Software Engineering" (and not CS) from the same university, but I think they heavily overlap in content, so in practice the point remains.
On my case beyond Architecture design, there was hardly any "how to write good code" lecture.
Recursion, good code and readable code are not related; I don't understand this point.
https://tinyletter.com/programmingphilosophy/letters/i-don-t...
How do you terminate?
for(;;) {
}Also break is no different from using return (to keep C syntax as example) when recursing.
If you guard break with if then you also need to prove if the "if" condition does indeed provide a dataflow path to break.
In all cases, for all possible inputs.
On the other hand, if that's what your for loop looks like, you probably have the same problem of proving that your recursion terminates (in all cases, for all possible inputs).
Iterative loops are much easier to analyze and reason about,
What Dijkstra had in mind was probably simple, syntactically constrained forms of loops, like for-loops where the loop variable is read-only in the loop body. They are simpler than general recursion, sure. But there are corresponding simpler forms of recursion, e.g. primitive recursion or tail recursion that are much simpler than general recursion.
iterative loops are believed to be easier to reason about.
My apologies for making an absolute statement with unclear terms, thus inviting uncharitable interpretations.
But simple loops are not as expressive as full loops (where you can modify the loop variable). As a simple example, try to phrase the Euclid's algorithm for computing the GCD using "for(int i = 0; i < n; i++) { ... }" where "i" is not modified in the loop body.
I'm really just advocating a rule of least power. Don't go into full general recursion just because you can.
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.
Agree completely, but want to bring it back to another computing topic: Technically, anything that can be computed with one Turing-complete language can be computed with another. And every language clearly is not equivalent in terms of ease of understanding and reasoning about as every other language.
Trivially, compare computations in brainfuck to computations in C. Compare the recursive definition of tree traversal available in lisps to languages without recursion (some BASIC variants and others) where you have to jump through hoops and self-manage a stack.
compare computations in brainfuck to computations in C.
You cannot use formal equivalence to prove
So in a hard way, the complexity of formal reasoning about the correctness of loops and recursion must be the same.
Note to self: This may not go down well here but I'm willing to take the flack.
> 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...
You can for example see how primitive things were back then by describing "mutable state" as "dynamic" and "immutable" as "static". Dynamic and static these days have entirely different connotations typically more associated with type systems.
Things have moved on and now in 2016 mutable state is increasingly being pushed out of codebases in favour of immutable practices. Recursion is (and always has been) one way of doing that.
:)
No. In fact, it's a huge problem in imperative code at all layers.
It's a bit of an apples-to-oranges comparison to compare (proper, bounded) for-loops to general recursion. A more appropriate question would be whether humans and computers find, say, primitive recursion or structural recursion easier to analyse and reason about than for-loops.
The difference between general- and primitive-recursion becomes very apparent when working in Coq, for example!
In Portuguese universities, by time you get to this programming issues you already had enough maths to be able to relate recursion to how mathematical proofs work.
At least it was so for me and most of my friends back in the 90's.
Often I find subtle bugs in my loops where as with recursion the compiler seems to pick them up for me.
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.
gcd(A, B) when B == 0 -> A;
gcd(A, B) when A < B -> gcd(B, A);
gcd(A, B) -> gcd(B, A rem B).
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.
[Edit: zap redundant sentence.]
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.