4 ms·

> Reliability was favored over other things (for example recursion was discouraged). This sounds really strange to me. So may I ask why? I find that recursion

> Reliability was favored over other things (for example recursion was discouraged). This sounds really strange to me. So may I ask why? I find that recursion - most of the time - helps shorten and clarify the code. Also, doesn't recursion make induction proofs trivial?

phleet 11y ago
It's a lot harder to reason about memory constraints on recursive programs. The clearness and correctness of the code often ignores the possibility for stack overflow. Most naive implementations of DFS will hit the stack limit given trees that are all one long path from a single root to a single leaf.
- mturmon 11y ago
  Further to your point, here's the guideline, and rationale, from Gerard Holzmann's document on recommended coding practices for C at NASA/JPL: 1. Rule: Restrict all code to very simple control flow constructs – do not use goto statements, setjmp or longjmp constructs, and direct or indirect recursion. Rationale: Simpler control flow translates into stronger capabilities for verification and often results in improved code clarity. The banishment of recursion is perhaps the biggest surprise here. Without recursion, though, we are guaranteed to have an acyclic function call graph, which can be exploited by code analyzers, and can directly help to prove that all executions that should be bounded are in fact bounded. (Note that this rule does not require that all functions have a single point of return – although this often also simplifies control flow. There are enough cases, though, where an early error return is the simpler solution.) This is rule 1 of 10, so he apparently feels strongly about "banishing recursion." Gerard was formerly at Bell Labs and is also a fellow of the ACM and a member of the NAE.
  - flogic 11y ago
    It's also important to note that these rules are made for critical control systems that tend to be low level. The cost benefit trade offs aren't going to be the same as in typical business software.
noir_lord 11y ago
The issue is largely that unbounded recursion is quite easy to do accidentally (in many of the languages that where used in the past) with the resulting stack smashing causing issues. Also many of these systems where hard real time as in "if we don't respond in under 30ms something expensive goes bang" and again recursion can cause problems with that, lots of these systems are interrupt driven and have no garbage collection or threading so you can't just pre-empt them in that event since by the time you spot the problem you blew through your deadline and something went bang.
- acomjean 11y ago
  Yup. We had some processes running with their own cpu with interrupts turned off, so if the process went weird it meant reboot (as we discovered the hard way one day). So we tried to keep code simple. On the plus side you had a pretty good idea about how long the max processing would take (and avoid the timeouts and aforementioned "bang"), as the OS couldn't interrupt us. Certain system calls couldn't be made while in what we called "soft real time". Memory allocation was done upfront. The process control of that system was interesting. You could assign processes to processors or groups of processors and then give those groups a scheduling method. I haven't seen anything like it in the years since I left.
eropple 11y ago
It's not a bad question, but approaching it from a CS perspective will cause you to blow your foot off--because it's not about code length or code clarity, it's about safety (which is orthogonal). Your stack's of a finite length, and eventually will grow into the heap unless your system has protections against it. In most systems lots of really important stuff is allocated at the bottom of the heap. It's very easy for a clobbered global flag (yes, hissss, globals, these are very constrained computers we're talking about here) to cause a system to have its shit get real at an alarming rate.
ArkyBeagle 11y ago
Every recursive algorithm has an equivalent iterative double. Iterative solutions ARE induction :) If you are careful about test vectors, you can pseudo-exhaustively prove that an iterative dual to a recursive algorithm is equivalent.
robotresearcher 11y ago
tldr version: Because you want (i) an acyclic function call tree of (ii) predictable depth.
- eropple 11y ago
  That reminds me--a friend was telling me earlier today about a piece of software he was working on that only allowed forward jumps. (It ensures that the program halts.)
  - TheLoneWolfling 11y ago
    It does slightly more than that - it provides a cheap computation of the upper bound of how long it will take.
    - eropple 11y ago
      Yeah, that too. Come to think of it, that was probably more his concern than just halting.
      - TheLoneWolfling 11y ago
        Going out on a limb here, but I don't suppose it was for a superoptimizer?
albinofrenchy 11y ago
In addition to what others have said here; often recursive calls can also trivially be optimized into loops by the compiler. This is very convenient in most cases, but could hide the fact that a direct recursive call will overflow your stack. This isn't apparent and would test out ok until someone makes a small; seemingly insignificant change which the compiler can't do tail call optimization on, and all of a sudden things fail.
VLM 11y ago
Non recursion is waaay "easier" to troubleshoot finite precision floating point issues and failures of the first part of "be liberal in what you accept and conservative in what you send". If you assume infinite precision arithmetic and a very friendly environment for inputs, recursion always looks simpler, but by the time you clean it up to handle real world issues, non recursion instead looks simpler. Its too easy to write recursive end conditions along the lines of "if x == 42" when your helpful floating point routine somehow mysteriously rounded x to 42.00000001 so it'll never equal, or "no (supposedly) UTF-16 encoded string would ever have an odd number of bytes, even though I have no control of the source and the source is known to occasionally be insane" or at least thats how I remember it. I've run into both. Its not funny at the time but in retrospect its usually fairly hilarious. Personally I think its harder for people to understand concurrency issues WRT recursion, but I'll probably just get flamed for that one. I feel more people have "leveled up" with concurrency and non-recursive code and functional style programming than have leveled up to include recursion in that mix. Imagine two (three?) concurrent recursive algos fighting each other over one data structure.

phleet 11y ago

It's a lot harder to reason about memory constraints on recursive programs. The clearness and correctness of the code often ignores the possibility for stack overflow. Most naive implementations of DFS will hit the stack limit given trees that are all one long path from a single root to a single leaf.

mturmon 11y ago
Further to your point, here's the guideline, and rationale, from Gerard Holzmann's document on recommended coding practices for C at NASA/JPL: 1. Rule: Restrict all code to very simple control flow constructs – do not use goto statements, setjmp or longjmp constructs, and direct or indirect recursion. Rationale: Simpler control flow translates into stronger capabilities for verification and often results in improved code clarity. The banishment of recursion is perhaps the biggest surprise here. Without recursion, though, we are guaranteed to have an acyclic function call graph, which can be exploited by code analyzers, and can directly help to prove that all executions that should be bounded are in fact bounded. (Note that this rule does not require that all functions have a single point of return – although this often also simplifies control flow. There are enough cases, though, where an early error return is the simpler solution.) This is rule 1 of 10, so he apparently feels strongly about "banishing recursion." Gerard was formerly at Bell Labs and is also a fellow of the ACM and a member of the NAE.
- flogic 11y ago
  It's also important to note that these rules are made for critical control systems that tend to be low level. The cost benefit trade offs aren't going to be the same as in typical business software.

noir_lord 11y ago

The issue is largely that unbounded recursion is quite easy to do accidentally (in many of the languages that where used in the past) with the resulting stack smashing causing issues. Also many of these systems where hard real time as in "if we don't respond in under 30ms something expensive goes bang" and again recursion can cause problems with that, lots of these systems are interrupt driven and have no garbage collection or threading so you can't just pre-empt them in that event since by the time you spot the problem you blew through your deadline and something went bang.

acomjean 11y ago
Yup. We had some processes running with their own cpu with interrupts turned off, so if the process went weird it meant reboot (as we discovered the hard way one day). So we tried to keep code simple. On the plus side you had a pretty good idea about how long the max processing would take (and avoid the timeouts and aforementioned "bang"), as the OS couldn't interrupt us. Certain system calls couldn't be made while in what we called "soft real time". Memory allocation was done upfront. The process control of that system was interesting. You could assign processes to processors or groups of processors and then give those groups a scheduling method. I haven't seen anything like it in the years since I left.

eropple 11y ago

It's not a bad question, but approaching it from a CS perspective will cause you to blow your foot off--because it's not about code length or code clarity, it's about safety (which is orthogonal). Your stack's of a finite length, and eventually will grow into the heap unless your system has protections against it. In most systems lots of really important stuff is allocated at the bottom of the heap. It's very easy for a clobbered global flag (yes, hissss, globals, these are very constrained computers we're talking about here) to cause a system to have its shit get real at an alarming rate.

ArkyBeagle 11y ago

Every recursive algorithm has an equivalent iterative double. Iterative solutions ARE induction :) If you are careful about test vectors, you can pseudo-exhaustively prove that an iterative dual to a recursive algorithm is equivalent.

robotresearcher 11y ago

tldr version: Because you want (i) an acyclic function call tree of (ii) predictable depth.

eropple 11y ago
That reminds me--a friend was telling me earlier today about a piece of software he was working on that only allowed forward jumps. (It ensures that the program halts.)
- TheLoneWolfling 11y ago
  It does slightly more than that - it provides a cheap computation of the upper bound of how long it will take.
  - eropple 11y ago
    Yeah, that too. Come to think of it, that was probably more his concern than just halting.
    - TheLoneWolfling 11y ago
      Going out on a limb here, but I don't suppose it was for a superoptimizer?

albinofrenchy 11y ago

In addition to what others have said here; often recursive calls can also trivially be optimized into loops by the compiler. This is very convenient in most cases, but could hide the fact that a direct recursive call will overflow your stack. This isn't apparent and would test out ok until someone makes a small; seemingly insignificant change which the compiler can't do tail call optimization on, and all of a sudden things fail.

VLM 11y ago

Non recursion is waaay "easier" to troubleshoot finite precision floating point issues and failures of the first part of "be liberal in what you accept and conservative in what you send". If you assume infinite precision arithmetic and a very friendly environment for inputs, recursion always looks simpler, but by the time you clean it up to handle real world issues, non recursion instead looks simpler. Its too easy to write recursive end conditions along the lines of "if x == 42" when your helpful floating point routine somehow mysteriously rounded x to 42.00000001 so it'll never equal, or "no (supposedly) UTF-16 encoded string would ever have an odd number of bytes, even though I have no control of the source and the source is known to occasionally be insane" or at least thats how I remember it. I've run into both. Its not funny at the time but in retrospect its usually fairly hilarious. Personally I think its harder for people to understand concurrency issues WRT recursion, but I'll probably just get flamed for that one. I feel more people have "leveled up" with concurrency and non-recursive code and functional style programming than have leveled up to include recursion in that mix. Imagine two (three?) concurrent recursive algos fighting each other over one data structure.