Why does NASA not allow recursion?

In an article by Gerard J. Holzmann, he talks about “Rules for Safety Critical Code“. You know, the type of code that sends things into outer space, or the type of code that keeps planes flying, or driverless trains moving. At the Jet Propulsion Lab, code is apparently written in C (why not Ada??). The first rule is the one of interest:

Rule: Restrict all code to very simple control flow constructs – do not use goto statements, setjmp or longjmp constructs, and direct or indirect recursion.

The rational is simple. Simple control-flow in a program is much easier to verify. If recursion is omitted from an algorithm Holzmann says that it is guaranteed to have there will be an “acyclic function call graph”. This rule likely exists because some recursive algorithms could be somewhat unpredictable. There is also the problem of resource use, which is problematic on things like interstellar probes with limited memory. Some have complained that this is a little too restrictive, citing that naturally recursive problems often become quite horrible when contorted to a non-recursive form that uses a stack. This is obviously true, but I doubt NASA needs to calculate Ackermann’s function or the Tower’s of Hanoi in space. Recursion is dangerous in places where you cannot access your machine.

NASA is not the only company to negate the use of recursion. In the coding standards for the C++ software development for the dysfunctional Joint Strike Fighter, Air Vehicle Rule 119 states “Functions shall not call themselves, either directly or indirectly (i.e. recursion shall not be allowed)”. Again for obvious reasons.

The other rule of interest is No.9, which says that the use of pointers should be restricted. Of course the problem with using recursion in safety critical code is just one consideration. Consider reading this article.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.