Recursion is as hard as mutable state to grasp if not harder.
We might find a few people who can do one thing sligtly better than the other one, but not complete blanks.
Some people can grok recursion in a functional programming language much faster and more easily than they would understand the concept of branching, variable assignment (with mutability) and non-pure functions (what we used to call "procedures" back in the day).
Hell, recursive quicksort and mergesort are easier to teach and remember than the iterative versions even in C and Java. They're divide-and-conquer algorithms, which makes them a natural fit for a recursive solution.
From cppreference.com: http://coliru.stacked-crooked.com/view?id=0b2cec4d8c69ffaf
So much teaching material for beginning programming is tainted by the cult of mutability that I have coworkers writing for loops instead of maps or the like for relatively trivial tasks. The end result is I have a harder time reading code, and the amount of possible bugs grows.
https://www.google.com/search?q=recursion+is+dangerous&rlz=1...
http://m.slashdot.org/story/198499
You can certainly dig up more information. For me, and this is just my opinion based on 35 years of software and hardware engineering, recursion is a neat academic idea but in the real world it is useless and dangerous.
I argue against your thought that recursion is useless, as well. It's a natural and intuitive solution for a lot of problems. The very concept of a dynamic programming solution starts with a recurrence relationship. It starts with recursion. Sorting algorithms are intutively recursive in many cases, Quicksort and Mergesort are just two examples.
And, 'dangerous' is an interesting term. I understand you've worked in embedded systems and hardware, and so those things are often critical systems that have to be super secure and completely bug free. Not every system is like that, though.
I want to understand why you believe that recursion is both useless and dangerous. Could you give some broad examples of the dangers of recursion from your years of experience?
Granted, you can write much more efficient code that can be tail call optimized, but there complex and less obvious. There are also languages which cache previous results so the native approch becomes O(n) with fairly elegant code that's still depth n.
PS: Anyway, tail call optimization only works when you can rewrite the code as a loop for more complex structures it's less useful.
You cannot turn a virtual tail call into a static jump.
PS: Feel free to look for any counter example.
Ok, create a loop equivalent for `(define (f g x) (g x))`.
Though the mechanical equivalent would be something like:
huge(input)
{
output, continue, current_function = f;
do{
if (current_function == f)
{input = x ; continue = true; current_function=g}
if (current_function == g)
{ output = input; continue = false;}
}while(continue);
return output;
}
The longer example is not great the point is it's a very language agnostic tradeoff of speed vs memory. Replace the ‘if’ conditionals with a case statement and its much faster you can speed it up further by using continue.
You can speed it up even more by having a jump at the end of each statement, but that stops looking like a loop and is basically just the tail call optimization.
Anyway, the important part is its low memory utilization and compiler independent.
PS: I in no way suggest tail call optimization was not useful; just you can mechanically simulate it when not available. You can usually beat that mechanical approach if you need to speed things up further.
But yet 10x slower than a single indirect jump.
> just you can mechanically simulate it when not available.
It's too slow to ever be anywhere near practical - for this reason, almost no JVM language implementation really does anything like this, besides kawa, bigloo and alike, which are slower than some of the dumb interpreters like SISC.
>"it's slow"
Again, it's just a technique; think writing embedded code with a really dumb compiler. Anyway, saying its slow is not really a counter argument if your limited to say 2,000 bytes of ram you will make lot's of tradeoffs between efficiency and speed. Perhaps you have a select statement perhaps you don't, but starting off with pure ASM is often a pain.
EDIT: This is all from the perspective of dealing with tools that don't do tail call optimization, not writing a compiler / VM etc.
Eventually you hit OOM or some death limit even on a stackless language.
Put another way, allocating 1GB of stack space on a machine with 2GB of RAM is at worst the equivelent of using a stackless lanugage on a machine limited 1 GB of RAM.
PS: It's actually worse as stackless languages are stricly slower than actually having the equivelent stack space pre alocated and you need to put an pointer for each stack call pluss overhead for alocating memory.
It's interesting that a bunch of people went off in a down-vote spree yet not one person offered a non-trivial use of recursion in commercial, medical or military software.
It wastes resources and it simply isn't safe. Used in the wrong place it can actually kill people.
Wrong.
> In the real world it is a bad idea.
Wrong. Your view of the real world is severely distorted.
> yet not one person offered a non-trivial use of recursion in commercial, medical or military software.
I suspect your 35 years of experience was 1 year repeated 35 times. Otherwise you would have known thousands of cases where recursion is unavoidable.
Take any real world compiler, for example. People nowadays are spoiled, they want meaningful error messages, they want semantic highlighting in IDEs, and so on. So forget about the dragon book, automatons and all such crap - your only option is a recursive descent parser.
If you want a guaranteed quality and proven correctness of your software (since you've mentioned medical and military), you have no other option but to use total languages. It's just too hard to reason about anything else. Which means - you only have recursion and no other means of control flow. Want your software to be 100% correct, robust and predictable - use recursion. I can go on forever, but things I've listed are already more than enough to debunk your point.
> It wastes resources
Wrong.
> and it simply isn't safe.
Wrong.
> Used in the wrong place it can actually kill people.
Incompetent coders kill people. Epileptoids suffering from severe forms of Dunning-Kruger effect kill people. Those who repeat 1 year of experience instead of building experience progressively kill people.
Said someone who does not even know what functional programming is. Hilarious.
I already told you that you can only prove correctness with total languages. Guess you not qualified enough to find any arguments to counter this point.
You continue to make a lame attempt to attack me instead of trying to understand the issue. Let me see if I can lend a perspective here. My prior posts were made from my iPad which is horrible for typing.
I can't remember how many programming languages I've used during my career. I started with machine language, moved to Forth, then C, APL, Lisp and C++ and Python. On the hardware front it's Verilog, but that's an HDL, which is irrelevant as it pertains to this discussion. The languages I listed above probably cover a huge chunk of my life's work. Of course, I've also worked extensively with what I call "web languages", mostly PHP and Javascript.
See any functional languages in that list? Yes, yes, I know they are "impure". Geez.
In the case of APL, this old paper deals with the question:
http://www.jsoftware.com/papers/eem/functional.htm
I worked with Lisp and APL professionally --not in an academic setting-- for about ten years. At the age of 20 I published my first paper at an international ACM conference on APL. I have a picture right here on my wall with Ken Iverson (boy did I look like a dork at 20!). That was 30 years ago!
Please stop insulting me.
Can one do recursion safely?
Yes. Absolutely. Without a doubt.
Wait a minute! Why, then, am I here saying the recursion is a bad idea and it is dangerous?
First you have to consider the fact that during the first, oh, twenty years of my career as a hardware/software engineer I designed things that could kill people if they failed catastrophically. That very quickly shifts your way of thinking. Screwing around with a website that can fail and nobody dies (and in a lot of cases, nobody cares) is very different from writing software for an industrial system that can cut a man in half. Very different. If you've never had that responsibility it might be hard to understand that elegance can be the enemy of safety.
Have you ever had to write software that considers the real-world possibility of a bit flipping in memory? And so my issue with recursion is one of theory vs. practice.
I like recursion. It can result in really elegant solutions when used in the right place and with proper safeguards. That last part is a hint as to where my opinion comes from. First, I'll let this very well respected post do some of the talking for me:
http://blog.codinghorror.com/why-cant-programmers-program/
So you have software engineers graduating from CS programs where they are shown the elegance and magic of recursion. They've "done" Fibonacci and a number of other assignments, parsers, etc. Now they get hired to work somewhere like, say, Toyota, and 90+ people die because he though it'd be neat to use unbounded recursion in the engine control system. But, of course, this programmer didn't make a conscious decision to actually use unbounded recursion. All he was taught was recursion. You, know, that neat Fibonacci trick? And so he used it, oblivious to the potential consequences. He had no idea of what was happening at a low level in the system.
Frankly, I can't remember any programming technique that has killed more people. I wouldn't even know how to search for that information. And the Toyota case might be the only publicly available case we have on recursion.
If the problem highlighted in the CodingHorror.com article is true, why would anyone willingly allow a programmer to use such a dangerous approach to solving a problem? I know, without a shadow of a doubt, what CodingHorror is talking about because I have founded and run three tech companies and have had the pleasure of having to hire both hardware and software engineers. I have to tell you, until you experience this, it's unbelievable. And then you hire them and you come to discover how much more they don't know.
Part of the disconnect is that a lot of programmers have no clue as to what is actually going on at the machine level. Those of use who came up through machine/assembly language and low level stuff like Forth learn this because, well, you have to. Someone starting life as a programmer with something like Python has ZERO idea of what is going on behind the curtains. He is taught recursion and it is hot-shit-neat and he is eager to use it somewhere to show his buddies just how smart he is. And that's how you can end-up with a situation like the Toyota problem or, less dramatically so, a library with hidden recursion that absolutely blows-up the system without the library's user having a clue that an unbounded recursive function is sitting there waiting for the right opportunity to cause a failure.
So I'll put it this way: Every experienced and capable engineer I know and have worked with will use recursion if, and only if, there is no other way to accomplish the same task. Where there is, it often is faster, less resource intensive and potentially safer. When there isn't, it must be tightly bounded and tested to failure. Introducing recursion into a mission critical piece of software means introducing something that must forever be in the back of your mind as a potential source of catastrophic failure.
Not a single one. Not even a functional language, not to mention total languages. Lisp does not qualify as a functional language and never even pretended to be one. And APL is a tacit one, quite a distant thing from anything functional.
Now, try to read my previous post carefully. Referring to the relevant literature when in doubt. My point, again:
the only practical way to have a program 100% proven to be correct, and at the same time avoid wasting hundreds of man-years developing it, is to develop it in one of the total languages. Which implies that the only mean of iteration you've got is recursion and nothing but recursion.
I.e., if you want to be 100% sure that your software and hardware will not kill, and will behave exactly as specified, then you must use recursion.
Yes, of course I'm perfectly aware of the reasons behind things like JPL coding standards. They're pretty outdated and should not be brought back now, in 21st century.
> Have you ever had to write software that considers the real-world possibility of a bit flipping in memory?
I did, as well as designing hardware with such a possibility in mind. Before things like HOL and ACL2 became available it was a total hell to do so. Now it's a piece of cake.
> So you have software engineers graduating from CS programs
And how recursion is responsible for idiotic HR policies? One should never hire graduate engineers for anything distantly mission-critical. Never.
> And so he used it, oblivious to the potential consequences.
This sort of people will screw up anyway, no matter what kind of tools they're allowed to use. Recursion is far below pretty much everything else on a list of things that an ignorant epileptoid can screw up, starting with off-by-one and pointer arithmetics.
And, leaving the embedded software aside, stack overflow is by far the least common issue out there, dwarfed by things like null pointer dereferencing and the said off-by-one.
> And so my issue with recursion is one of theory vs. practice.
Practice is irrelevant. It will never give you a full coverage of all the things you can potentially screw up, not even with hundreds of years of experience. Theory, on contrary, is perfectly capable of doing so.
> Frankly, I can't remember any programming technique that has killed more people.
Magic constants. Perverted approach to parallelism (shared memory instead of message passing). Google for "Therac-25" for example.
> why would anyone willingly allow a programmer to use such a dangerous approach to solving a problem?
Where the other means of ensuring correctness are not available, the right coding standards are more or less ok (the said JPL coding guidelines for example).
> Those of use who came up through machine/assembly language and low level stuff like Forth learn this because, well, you have to.
Can you imagine someone without this kind of background allowed to meddle with a mission-critical embedded software? I'm not aware of such cases, and I spent quite a few years in predominantly embedded environment.
> if, and only if, there is no other way to accomplish the same task.
Bingo. In the total languages there is no other way to accomplish, well, anything. And only the total languages are safe enough for the mission-critical software and hardware. Turing-completeness is evil - this is what you should have been attacking, not the innocent recursion.
> Introducing recursion into a mission critical piece of software means introducing something that must forever be in the back of your mind as a potential source of catastrophic failure.
Human mind is a broken tool and should not be allowed to judge a quality of a software. Formal logic is much better in ensuring that the software behaves exactly as prescribed.
Let's just agree to disagree.
???
My "theory" is being extremely widely used in practice. Take a look at the Intel FDIV bug history and its consequences for example. They've been formally certifying critical parts of the hardware ever since then.
Or take a look at the widely used seL4 kernel: http://ssrg.nicta.com.au/projects/seL4/
> In practice the vast majority of code is NOT written in total languages.
And this is the problem, not recursion or whatever else. Incompetent coders are evil, and you cannot blame any particular technique for any failures. Luckily, in my practice, nobody ever dared to let any graduate larvae to hang anywhere near any kind of mission-critial code. I've heard stories, of course, but never witnessed anything like that myself.
> they decide there's this recursion thing they read about or learned in school.
As I said, people of this degree of cognitive development will screw up anyway, no matter what techniques they use. In a monkey with a hand grenade situation you should not worry too much about a sharp stick this monkey may accidentally pick up.
> the injection of recursion by the wrong people is dangerous
Pretty much everything else they do is equally or more dangerous anyway.
And, getting back to your rant which started this thread - you said that recursion is dangerous and useless. Unconditionally.
Now it turns out that it may be dangerous, but only when used by complete tools and only in heavily mission-critical embedded projects. Quite a distance from what you've said originally. No wonder you've got such a response.
The world you paint isn't the real world. The world I am considering is this one:
In other words, one where your total languages are virtually nowhere to be found. Not by a small margin, by a landslide.
So, as they say in the movies, in a world where the top 5 most used languages are C and and C derivatives and total languages are almost nowhere to be found or a thing of academia, then, yes, what I am saying is very relevant and, dare I say, true and appropriate.
And, BTW, even experienced programmers screw up recursion because it just isn't used that often. I don't want to blame newbies.
So I look at this world, as evidenced by the charts on that site and a data I am sure could be dug up on a bunch of other sites I can very easily conclude that total languages are still mostly in academia and so is safe recursion. In a world dominated by C and derivatives, recursion can be really dangerous. Bad recursion hidden inside a library can be really bad news.
Anyhow, I am done with the back and forth. I understand where you want to come from. I am just asking that you understand that the frame of reference you have constructed is not one that matches our current reality. Which means one can't say that recursion is safe because when total languages when virtually nobody, in relative terms, uses them. And then, when they do use them, you have to ask what they are using them for. Is it Academia or real world application?
Enough said. Thanks for a good discussion. I wish people were not so nasty with down-votes on HN as it detracts from trying to have a discussion based on ideas contrary to the underlying HN culture. That's just the way it is.
My world is this one:
http://www.prover.com/company/press/view/?id=47
http://www.cl.cam.ac.uk/~jrh13/slides/nasa-14apr10/slides.pd...
... and so on.
And, honestly, I don't want to have anything in common with your "real world", where graduate larvae with IQ < 80 is allowed to code automotive microcontrollers.
> In other words, one where your total languages are virtually nowhere to be found.
We're speaking about mission critical stuff, which is already a virtually nonexistent thing dwarfed by CRUD and all such crap.
> And, BTW, even experienced programmers screw up recursion because it just isn't used that often. I don't want to blame newbies.
I see. You did not get a single word from what I said. Pity.
Let me repeat my point again: humans are brainless scumbags. They should never be trusted with anything important. If anything can be screwed up, it will be screwed up in an epic scale. The only way to avoid an epic screwup is to exclude this brainless scum from the process, and let the immaculate formal systems do the job.
> I am just asking that you understand that the frame of reference you have constructed is not one that matches our current reality.
I'd prefer to stay away as far as possible from your reality. Mine is much better. In my reality, a code without multiple layers of formal proof would not ever be signed off for anything mission critical (although I admit that the most deadly stuff I worked with were anti-aircraft systems, nothing fancy like nuclear plants and such).
And what's your standing regarding the total languages? How dangerous is, say, Agda2? How useless is HOL?
Of course, you can explicitly demand totality, and it's perfectly fine, but still it is quite a severe limitation, and you'll have to allow optional unrestricted recursion if you want to have (at leat local) Turing completeness.