Hacker News Reader

Comment by myth_buster | Hacker News Reader

You are not alone. NASA/JPL explicitly prohibits it in their coding standards [0].

  Rule 4 (recursion)
  There shall be no direct or indirect use of recursive function calls.
  [MISRA-C:2004 Rule 16.2; Power of Ten Rule 1]

  The presence of statically verifiable loop bounds and the absence of recursion 
  prevent runaway code, and help to secure predictable performance for all 
  tasks. The absence of recursion also simplifies the task of deriving reliable 
  bounds on stack use. The two rules combined secure a strictly acyclic function 
  call graph and control-flow structure, which in turn enhances the capabilities 
  for static checking tools to catch a broad range of coding defects.

[0] http://lars-lab.jpl.nasa.gov/JPL_Coding_Standard_C.pdf

View on HN

Though, for context, here's the first paragraph after the introduction:

  The coding rules defined here primarily target the development of mission 
  critical flight software written in the C programming language. This means 
  that the rules are focused on embedded software applications, which 
  generally operate under stricter resource constraints than, e.g., ground 
  software.

I don't think it's at all surprising that the coding standards governing critical software running in resource-constrained environments should be so conservative. But I also don't know that the priorities motivating those standards generalize well to what most programmers do for a living.

Recursion is prohibited in embedded contexts because it allows for, potentially, unbounded growth of the call stack. In the embedded world we have to know how much space things need. You'll note they also ban malloc. But few would suggest that every C programmer should abandon malloc in their software.

> Recursion is prohibited in embedded contexts because it allows for, potentially, unbounded growth of the call stack.

Only if you're sloppy about the inputs given to the recursive code.

Recursion isn't magical. It's deterministic, and is a function of some aspect of the input values. (Corollary: If it isn't, what the fuck are you doing?)

So NASA decided to solve the stack growth problem by limiting recursion. (Zero is a limit.) It could have done the other thing and limited inputs to recursive code, which would have required more careful code analysis (static and dynamic) to figure out what the limits should be. It's an understandable decision, but don't forget it's a trade-off, and one that could have gone another way.

Sure, it's deterministic. But in embedded contexts we typically have no malloc either, and often operate in very memory constrained environments. By removing recursion and favoring iteration you know the size of your stack at any given point in program execution. There is no size range that you have to consider (for instance, by limiting recursion to a depth of 20 for a particular algorithm or something). We also have to remember that TCO is not, or historically not, guaranteed in C compilers, the language in question.

So any recursive algorithm using tail-calls would be better implemented as a for/while loop in embedded C contexts, the performance will be similar (should actually be better) and the memory is now constant instead of increasing.

Any recursive algorithms that can't use tail-calls, I'm honestly not thinking of common situations for these in an embedded context. Perhaps traversing certain data structures, but you can probably find a different data structure that will be sufficiently efficient and not require non-tail-calls. Even with sorting, if you have a small, fixed sized array you could implement a sorting network. If it's too large for that to be feasible in code, it's probably still a small enough array that insertion sort is efficient.

>It could have done the other thing and limited inputs to recursive code, which would have required more careful code analysis (static and dynamic) to figure out what the limits should be. It's an understandable decision, but don't forget it's a trade-off, and one that could have gone another way.

I don't see the trade-off.

On one hand (if you allow recursion) you need "more careful code analysis".

On the other hand, if you don't allow it, you don't lose anything. You can write the algorithm in another way, and it would be just as fast and easier to reason about.

So what's the tradeoff? It's not like recursion brings some benefit that you lose if you disallow it.

> On the other hand, if you don't allow it, you don't lose anything. You can write the algorithm in another way, and it would be just as fast and easier to reason about.

This is where we differ, then: Some algorithms are more natural to write recursively. Sorting is a big example.

Reply on news.ycombinator.com