[rebootthesystem]

In 35 years of programming across platforms and languages covering embedded to web applications it is my opinion that recursion is dangerous and useless. There is no way I would use recursion to evaluate how good a programmer might be. To quote the movie: "Frankly dear, I don't give a damn".

[sklogic]

Do you imply that functional programming in general is dangerous and useless?

And what's your standing regarding the total languages? How dangerous is, say, Agda2? How useless is HOL?

[rebootthesystem]

Nothing whatsoever to do with functional programming.

[sklogic]

How is it so? Recursion is the only possible form of iterative control flow in the functional languages. If you do not want to allow any forms of recursion, you cannot use functional languages at all.

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.

[chrismcb]

Recursion is a tool. It can be misused, but it is just a tool. And sometimes it can be very useful.

[rebootthesystem]

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.

[sklogic]

> Recursion is mostly an academic tool.

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.

[rebootthesystem]

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.

[sklogic]

> Take a moment to educate yourself

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.

[rebootthesystem]

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:

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.

[mytochar]

Why?

[rebootthesystem]

Just so I can answer, why what?

[rebootthesystem]

Just in case this is what you were trying to understand:

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.

[mytochar]

I'm seeing stack overflows (not a problem with tail-call optimization) as the biggest problem here. There are equally dangerous problems, though. Buffer overflows are a very real concern, especially in embedded software; but that doesn't mean that people don't ever use pointers. Everything about software has risks. Yes, they probably shouldn't have used recursion there in that car; but honestly, it's just a stack. Enough calls and some state could have been frozen. They should have put mitigations in place to stop the potential for a stack overflow to have actual, detrimental results. Do you refuse to ever make a function call for fear that you might be at the top of the stack somehow? After all, how can you know that you haven't accidentally created a state machine with function calls and are at the peak of it now, and end up causing the same problem. Recursion may have been the final manifestation, but it's certainly not the only place that failed.

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?

[Retric]

It's trivial to blow the stack even on languages with tail call optimization.

[sklogic]

Ok, try to blow the stack in a stackless language implementation.

[Retric]

F(x) = F(x) + F(x)

Eventually you hit OOM or some death limit even on a stackless language.

[mytochar]

By writing incorrect recursion? Or in some other way?

[Retric]

Both, the obvious example is the fibinatchi sequence f(x) = f(x-1) + f(x-2). There are lots of efficient ways of coding it but the most obvious O(n^2) approch is n depth and it can't be tail-call optimized.

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.

[sklogic]

And how exactly it is related to recursion? You should have said "memory leaks are dangerous", and everyone would agree.