6 ms·

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

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".

mytochar 12y ago
Why?
- rebootthesystem 12y ago
  Just so I can answer, why what?
- rebootthesystem 12y ago
  Just in case this is what you were trying to understand: https://www.google.com/search?q=recursion+is+dangerous&rlz=1C9BKJA_enUS590US591&oq=recursion+is+danger&aqs=chrome.1.69i57j0&sourceid=chrome-mobile&espv=1&ie=UTF-8&hl=en-US https://www.google.com/search?q=recursion+is+dangerous&rlz=1... http://m.slashdot.org/story/198499 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 12y ago
    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 12y ago
      It's trivial to blow the stack even on languages with tail call optimization.
      - mytochar 12y ago
        By writing incorrect recursion? Or in some other way?
        Retric 12y ago
        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 12y ago
        > Anyway, tail call optimization only works when you can rewrite the code as a loop You cannot turn a virtual tail call into a static jump.
        Retric 12y ago
        Sure, it needs bookkeeping but it's still trivial to create a loop equivalent of any tail call optimizable code that your compiler recognizes. PS: Feel free to look for any counter example.
        sklogic 12y ago
        > PS: Feel free to look for any counter example. Ok, create a loop equivalent for `(define (f g x) (g x))`.
  - sklogic 12y ago
    And how exactly it is related to recursion? You should have said "memory leaks are dangerous", and everyone would agree.
chrismcb 12y ago
Recursion is a tool. It can be misused, but it is just a tool. And sometimes it can be very useful.
- rebootthesystem 12y ago
  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 12y ago
    > 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 12y ago
      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 12y ago
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 12y ago
  Nothing whatsoever to do with functional programming.
  - sklogic 12y ago
    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.

mytochar 12y ago

Why?

rebootthesystem 12y ago
Just so I can answer, why what?
rebootthesystem 12y ago
Just in case this is what you were trying to understand: https://www.google.com/search?q=recursion+is+dangerous&rlz=1C9BKJA_enUS590US591&oq=recursion+is+danger&aqs=chrome.1.69i57j0&sourceid=chrome-mobile&espv=1&ie=UTF-8&hl=en-US https://www.google.com/search?q=recursion+is+dangerous&rlz=1... http://m.slashdot.org/story/198499 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 12y ago
  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 12y ago
    It's trivial to blow the stack even on languages with tail call optimization.
    - mytochar 12y ago
      By writing incorrect recursion? Or in some other way?
      - Retric 12y ago
        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 12y ago
        > Anyway, tail call optimization only works when you can rewrite the code as a loop You cannot turn a virtual tail call into a static jump.
        Retric 12y ago
        Sure, it needs bookkeeping but it's still trivial to create a loop equivalent of any tail call optimizable code that your compiler recognizes. PS: Feel free to look for any counter example.
        sklogic 12y ago
        > PS: Feel free to look for any counter example. Ok, create a loop equivalent for `(define (f g x) (g x))`.
- sklogic 12y ago
  And how exactly it is related to recursion? You should have said "memory leaks are dangerous", and everyone would agree.

chrismcb 12y ago

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

rebootthesystem 12y ago
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 12y ago
  > 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 12y ago
    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 12y ago

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 12y ago
Nothing whatsoever to do with functional programming.
- sklogic 12y ago
  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.