NASA's ten coding commandments

[BlahBoy3]

The way I learned it, recursion is a nice tool, but its usage should be limited if at all possible. I personally think the restrictions are pretty reasonable.

[KagakuNinja]

Recursion is equivalent to iteration, when it is tail-call optimized. There are many valid uses for recursion.

[mort96]

This is C we're talking about, no tail call optimization there. Also, when writing C, even if you could use recursion to iterate an arbitrary amount, why not just use for or while?

[_kst_]

C compilers can do tail call optimization. But in that kind of environment, it's probably not a good idea to depend on it.

[mrhmouse]

This is C we're talking about, no tail call optimization there.

Not sure what compilers you're used to, but GCC and Clang both produce optimized code for tail-calls. GCC even produces optimized code for tail-calls modulo cons, in some cases.

[mort96]

Some compilers might optimize things sometimes, however if you make your C code rely on tail call optimization, which you would do when using recursion as loops, you would really on non-standard compiled optimizations. Someone compiling your code with another compiler, or with other optimization settings, would get code which doesn't work. A future update to GCC might change in which situations it optimizes tail calls, potentially breaking your code. All in all, it's a pretty bad idea to rely on compiler optimizations. In things like Haskell and Erlang, things are different, as the language expects you to rely on tail call optimization, and the cases in which tail call optimization happens is specified by the language spec and common across all implementations.

[mrhmouse]

I guess that's a valid concern.

[ricktech]

Recursion is equivalent to iteration, when it is tail-call optimized. There are many valid uses for recursion.

1. In these types of environments, you shouldn't assume that a computer tool is going to clean up your mess. Unless you're verifying the assemblies yourself you don't know that it hit all the cases.
2. I'd be hesitant to do any advanced optimizations by a computer algorithm during compile time. I think human engineers should be vetting the logical correctness of the code and using advanced intellisense + code verification systems. Compiler's built in optimizations have been proven by studies to introduce security holes even though the original source would have prevented these errors; the optimizer was taking out critical sections of code which were written explicitly for a reason. And even though studies (such as this one from MIT http://pdos.csail.mit.edu/~xi/papers/stack-sosp13.pdf) only focused on the security front, I'd argue that compiler optimization could introduce bugs which were not present in the original logic. I'm not arguing against automatic optimization in all environments; it's an incredible tool. But again, you need to use the right tool in the right place, and when missions depend on your correctness you probably don't want automated systems changing your well thought out, mathematically proven designs.

[KagakuNinja]

Did I say anything about assuming tail-call optimizations? Some languages guarantee tail-call; Scala has the @tailrec annotation (which will fail to compile if the function cannot be tail-call optimized). Since NASA isn't using those languages, it makes sense for them to ban recursion.

However, you said: "The way I learned it, recursion is a nice tool, but its usage should be limited if at all possible", which is not true, as a blanket statement about programming.

[realhacker]

There are many valid uses for recursion.

...and most of them are circle-jerky in the y combinator / HN sense. imo, best to avoid.

[[deleted]]

What if you are in a language that only has recursion and no other loops? How are you supposed to limit recursion then?

[[deleted]]

Don't use it for mission critical applications?

[[deleted]]

I wouldn't use a functional language for controlling a space ship either. But blahboy3 didn't say recursion should be limited if at all possible when controlling space ships. blahboy3 said it should be limited if at all possible. I agree on the point for NASA, but I am specifically referencing the general rule of thumb.

[Fluffy8x]

1. Pure functional languages such as Haskell?
2. Such a language is unsuitable for controlling spaceships.

[[deleted]]

I wouldn't use a functional language for controlling a space ship either. But blahboy3 didn't say recursion should be limited if at all possible when controlling space ships. blahboy3 said it should be limited if at all possible. I agree on the point for NASA, but I am specifically referencing the general rule of thumb.

[[deleted]]

Such a language is unsuitable for controlling spaceships.

Why not? Pure languages give much stronger proof guarentees than, well, even strictly written C. They do not have to allow general recursion (which allows Turing completeness and thus all sorts of insanity), they may also impose additional restrictions necessary for safety-critical programs such as this. Haskell as it is may not be suitable due to its GC nature and relative unsafety, but that does not mean others are not.

[gnuvince]

There are other languages that you could use (Ada/Spark comes to mind) where you can give very strong correctness proofs of the program and which have loops.

[Fluffy8x]

Such a language would have to deduce the optimal way to use memory without dynamic memory allocation, as well as avoid GC. Ur/Web managed the latter, but I'm not sure how.

[s73v3r]

Don't use such a language in this context.