Iterative loops are much easier to analyze and reason about, by humans and by computers. For example, they always terminate. To paraphrase Dijkstra, "I regard general recursion as an order of magnitude more complicated than just repetition, and I don't like to crack an egg with a sledgehammer."
He actually discusses it a bit in the previous paragraph, which does not seem to be online anywhere:
> 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.)
Iterative loops are much easier to analyze and reason about,
This is not the case. Loops and recursion can be translated into each other, hence are of equal complexity in terms of reasoning. And you see that when you write down the Hoare-logic axioms for either.
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.
> Loops and recursion can be translated into each other...
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.
Yes, that is the point I tried to make. Use simple, constrained forms such as (C) "for(int i = 0; i < n; i++) { ... }" with n an int and no modification of i in the body, or (Python) "for e in l:" where l is a list that is not modified in the body. Then your code is very easy to analyze, not just in theory but also in practice for compilers, tools and people reading your code. Many language designers have realized this and provide special syntax for this very common case. I'm not aware of any language that has special syntax for primitive recursion, but it's an interesting idea.
My apologies for making an absolute statement with unclear terms, thus inviting uncharitable interpretations.
Why is this being down-voted? Could somebody please explain why they think what I wrote is wrong? I'd be happy to learn something new about loops and recursion.
> Iterative loops are much easier to analyze and reason about, by humans and by computers. For example, they always terminate.
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!
nbevans|10 years ago
Note to self: This may not go down well here but I'm willing to take the flack.
rer0tsaz|10 years ago
> 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...
pjmlp|10 years ago
How do you terminate?
meggar|10 years ago
mafribe|10 years ago
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.
AnimalMuppet|10 years ago
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.
rer0tsaz|10 years ago
My apologies for making an absolute statement with unclear terms, thus inviting uncharitable interpretations.
mafribe|10 years ago
nilved|10 years ago
chriswarbo|10 years ago
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!
_pmf_|10 years ago
No. In fact, it's a huge problem in imperative code at all layers.