12 ms·

> Whats complicated about an iteration What’s complicated about a recursion? > If you see problems, its because something is modifying it between runs, but th

> Whats complicated about an iteration What’s complicated about a recursion? > If you see problems, its because something is modifying it between runs, but that wasn't a fault of the iterative strategy, it was the fault of a bad programmer. > Conversely, you must always make sure the stopping condition and all base cases are met during recursion. You seem to be applying a double standard here. > Forget one corner base case and you got a rare production bug. Base cases are usually much easier to reason about.

blackflame7000 8y ago
Then why does NASA consider it unsafe for mission critical code? How about unknown potential stack size? How about factoring a large number with recursion? Everything recursive can be transformed to iterative and yea sometimes it’s not as sexy but neither is a helmet https://www.reddit.com/r/programming/comments/3dnsh1/nasas_ten_coding_commandments/ https://www.reddit.com/r/programming/comments/3dnsh1/nasas_t...
- throwaway37585 8y ago
  > Then why does NASA consider it unsafe for mission critical code? They also proscribe unbounded iterations (point 2). In any case, NASA’s guidelines for mission-critical code are not necessarily good guidelines for general software engineering, given the constraints involved. It’s also worth noting that recursive solutions are probably more amenable to static analysis and automated theorem proving. > How about unknown potential stack size? If stack size is a problem, try an iterative solution. > How about factoring a large number with recursion? Go with iteration. You keep editing your answer to add more cases where iteration is the way to go. I’m not disputing there are use cases where iteration is appropriate.
  - throwaway344534 8y ago
    Ok so thank you for admitting that Recursion presents more risks than iteration and requires a programmer wise to those risks. Therefore proving that iterative is the cheaper and easier method that should be used the majority of the time. At the end of the day, saving a few lines of code to be cleaver is an all risk no reward situation other than to flaunt your ePenis to your co-workers
  - danmg 8y ago
    > Then why does NASA consider it unsafe for mission critical code? More like they're using an old Fortran 77 environment which doesn't support recursive functions.
    - deleted 8y ago
      [deleted]
    - throwaway344534 8y ago
      More like they were using C, saw the prospect of unbounded stack calls unreasonable with a computer with limited ram and banned recursion. Oh wait that's exactly what happened because iteration is safer than recursion.
      - dahart 8y ago
        Iteration is not inherently safer than recursion. NASA also banned while(true) iteration. The important part is "fixed upper bounds". "Give all loops a fixed upper bound. It must be trivially possible for a checking tool to prove statically that the loop cannot exceed a preset upper bound on the number of iterations. If a tool cannot prove the loop bound statically, the rule is considered violated." https://pdfs.semanticscholar.org/ad40/26510beb1a30990270458387e769e216dca3.pdf https://pdfs.semanticscholar.org/ad40/26510beb1a309902704583...
        monocasa 8y ago
        The static analysis tools have a harder time parsing the upper bounds on recursive functions, and so do the engineers doing the code reviews for similar reasons. This isn't just a NASA thing. Pretty much any embedded coding standard says the same thing. The JSF C++ standard, and MISRA-C I know both do as well, just off the top of my head.
    - dahart 8y ago
      No that's incorrect. Their rules are C guidelines, and they are easy to Google. You might want to do that before making assumptions. NASA's rules, the ones being referenced above, are designed for safety. They require code to be easy to statically analyze and to have absolutely predictable behavior. Also to be avoided: memory allocation, unbounded loops, function pointers, preprocessor macros. https://en.wikipedia.org/wiki/The_Power_of_10:_Rules_for_Developing_Safety-Critical_Code https://en.wikipedia.org/wiki/The_Power_of_10:_Rules_for_Dev...
- jacquesm 8y ago
  That's a restriction on the environment which has absolutely nothing to do with how readable a certain piece of code is. In fact it argues the opposite: we force you to use a less readable version of your code because the elegant one may be easier to read but it may have negative consequences due to implementation details. That's a really good trade-off for them but it does not necessarily help readability.
  - blackflame7000 8y ago
    But then your code is not portable because it is now susceptible to arbitrary stack depth changes blowing up your program. None of your arguments make sense when compared with the overwhelmingly superior iterative approach. Recursion is the same as iteration + downsides. I mean seriously name the last time you had a stack overflow and weren't doing recursion? That's an entire class of bug introduced or eliminated by a simple design decision. That's how you write superior code for now and in the future. You shouldn't have to know about the implementation when writing portable code. If you introduce recursion, you now need to worry about implementation since the machine max stack size is now an issue and you've broken the abstraction. And what exactly did you gain that outweigh's the cons?
    - jacquesm 8y ago
      You are confusing implementation of a language with readability. And I honestly don't remember the last time I had a stack overflow, there is something known as tail-call optimization. https://en.wikipedia.org/wiki/Tail_call https://en.wikipedia.org/wiki/Tail_call
- pvg 8y ago
  Then why does NASA consider it unsafe for mission critical code? You started with the assertion iterative implementations were more intuitive and easier to read so this is a bit of goalpoast-moving. Write an iterative pseudocode DFS or quicksort. How 'intuitive' does that look?
  - blackflame7000 8y ago
    I'm saying that there are so many downsides both obvious and sneaky associated with recursion that it makes almost no sense to use when the iterative approach is usually safer, doesn't have the headache of unbounded stack calls, and can be more easily parallelized with things like OpenMP
    - pvg 8y ago
      That's what you are saying now, this is what you were saying before: " I'm willing to bet most people if shown 10 recursive and 10 iterative solutions to the same problems would admit the iterative approach is more intuitive. " Now you are at NASA sending probes to asteroid Weasel 39812.
davidgay 8y ago
> > Whats complicated about an iteration > What’s complicated about a recursion? Especially as iteration is just a special case of recursion :)

blackflame7000 8y ago

Then why does NASA consider it unsafe for mission critical code? How about unknown potential stack size? How about factoring a large number with recursion? Everything recursive can be transformed to iterative and yea sometimes it’s not as sexy but neither is a helmet https://www.reddit.com/r/programming/comments/3dnsh1/nasas_ten_coding_commandments/ https://www.reddit.com/r/programming/comments/3dnsh1/nasas_t...

throwaway37585 8y ago
> Then why does NASA consider it unsafe for mission critical code? They also proscribe unbounded iterations (point 2). In any case, NASA’s guidelines for mission-critical code are not necessarily good guidelines for general software engineering, given the constraints involved. It’s also worth noting that recursive solutions are probably more amenable to static analysis and automated theorem proving. > How about unknown potential stack size? If stack size is a problem, try an iterative solution. > How about factoring a large number with recursion? Go with iteration. You keep editing your answer to add more cases where iteration is the way to go. I’m not disputing there are use cases where iteration is appropriate.
- throwaway344534 8y ago
  Ok so thank you for admitting that Recursion presents more risks than iteration and requires a programmer wise to those risks. Therefore proving that iterative is the cheaper and easier method that should be used the majority of the time. At the end of the day, saving a few lines of code to be cleaver is an all risk no reward situation other than to flaunt your ePenis to your co-workers
- danmg 8y ago
  > Then why does NASA consider it unsafe for mission critical code? More like they're using an old Fortran 77 environment which doesn't support recursive functions.
  - deleted 8y ago
    [deleted]
  - throwaway344534 8y ago
    More like they were using C, saw the prospect of unbounded stack calls unreasonable with a computer with limited ram and banned recursion. Oh wait that's exactly what happened because iteration is safer than recursion.
    - dahart 8y ago
      Iteration is not inherently safer than recursion. NASA also banned while(true) iteration. The important part is "fixed upper bounds". "Give all loops a fixed upper bound. It must be trivially possible for a checking tool to prove statically that the loop cannot exceed a preset upper bound on the number of iterations. If a tool cannot prove the loop bound statically, the rule is considered violated." https://pdfs.semanticscholar.org/ad40/26510beb1a30990270458387e769e216dca3.pdf https://pdfs.semanticscholar.org/ad40/26510beb1a309902704583...
      - monocasa 8y ago
        The static analysis tools have a harder time parsing the upper bounds on recursive functions, and so do the engineers doing the code reviews for similar reasons. This isn't just a NASA thing. Pretty much any embedded coding standard says the same thing. The JSF C++ standard, and MISRA-C I know both do as well, just off the top of my head.
  - dahart 8y ago
    No that's incorrect. Their rules are C guidelines, and they are easy to Google. You might want to do that before making assumptions. NASA's rules, the ones being referenced above, are designed for safety. They require code to be easy to statically analyze and to have absolutely predictable behavior. Also to be avoided: memory allocation, unbounded loops, function pointers, preprocessor macros. https://en.wikipedia.org/wiki/The_Power_of_10:_Rules_for_Developing_Safety-Critical_Code https://en.wikipedia.org/wiki/The_Power_of_10:_Rules_for_Dev...
jacquesm 8y ago
That's a restriction on the environment which has absolutely nothing to do with how readable a certain piece of code is. In fact it argues the opposite: we force you to use a less readable version of your code because the elegant one may be easier to read but it may have negative consequences due to implementation details. That's a really good trade-off for them but it does not necessarily help readability.
- blackflame7000 8y ago
  But then your code is not portable because it is now susceptible to arbitrary stack depth changes blowing up your program. None of your arguments make sense when compared with the overwhelmingly superior iterative approach. Recursion is the same as iteration + downsides. I mean seriously name the last time you had a stack overflow and weren't doing recursion? That's an entire class of bug introduced or eliminated by a simple design decision. That's how you write superior code for now and in the future. You shouldn't have to know about the implementation when writing portable code. If you introduce recursion, you now need to worry about implementation since the machine max stack size is now an issue and you've broken the abstraction. And what exactly did you gain that outweigh's the cons?
  - jacquesm 8y ago
    You are confusing implementation of a language with readability. And I honestly don't remember the last time I had a stack overflow, there is something known as tail-call optimization. https://en.wikipedia.org/wiki/Tail_call https://en.wikipedia.org/wiki/Tail_call
pvg 8y ago
Then why does NASA consider it unsafe for mission critical code? You started with the assertion iterative implementations were more intuitive and easier to read so this is a bit of goalpoast-moving. Write an iterative pseudocode DFS or quicksort. How 'intuitive' does that look?
- blackflame7000 8y ago
  I'm saying that there are so many downsides both obvious and sneaky associated with recursion that it makes almost no sense to use when the iterative approach is usually safer, doesn't have the headache of unbounded stack calls, and can be more easily parallelized with things like OpenMP
  - pvg 8y ago
    That's what you are saying now, this is what you were saying before: " I'm willing to bet most people if shown 10 recursive and 10 iterative solutions to the same problems would admit the iterative approach is more intuitive. " Now you are at NASA sending probes to asteroid Weasel 39812.

davidgay 8y ago

> > Whats complicated about an iteration > What’s complicated about a recursion? Especially as iteration is just a special case of recursion :)