Recursion is mostly an academic tool. In the real world it is a bad idea.
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. 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.
Very nice attempt at shooting the messenger to attempt to make a really lame point. Of course ypu can use recursion in non mission critical applications such as a compiler. Take a moment to educate yourself as to the requirements for industrial, medical and military devices and you might begin to understand. And, BTW, we don't have to agree, that's the beauty of it. You can go on beleiving you are right and I can now see about repeating that one year of experience for the 36th. time.
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.
I asked you to educate yourself as to the issues and requirements of software used in the context of a system or device that could kill people. In this context industrial, medical and military applications are the most obvious places where you will find these kinds of systems. I have worked in all three of these domains in my 35 years of, as you suggested, repeating one year of experience. And, BTW, I am not just a software engineer, I quite often design the very hardware these software systems have to run on, which for the past 15 years or so has usually meant some rather massive Xilinx FPGA's with embedded processors, etc.
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:
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:
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.
You see, i am arguing from practice and you from theory. In theory you are absolutely correct. In practice the vast majority of code is NOT written in total languages. A more likely scenario is one where somebody is using language X and, in the middle of a project they decide there's this recursion thing they read about or learned in school. And off they go. In that context. In the context of a practical world where virtually nobody is is using total languages, the injection of recursion by the wrong people is dangerous. I say this from first hand experience.
> You see, i am arguing from practice and you from theory.
???
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.
> 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.
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.
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).
