3 ms·

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

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 http://lars-lab.jpl.nasa.gov/JPL_Coding_Standard_C.pdf

bunderbunder 11y ago
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.
Jtsummers 11y ago
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.
- cbd1984 11y ago
  > 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.
  - coldtea 11y ago
    >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.
    - cbd1984 11y ago
      > 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.
  - Jtsummers 11y ago
    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.

bunderbunder 11y ago

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.

Jtsummers 11y ago

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.

cbd1984 11y ago
> 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.
- coldtea 11y ago
  >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.
  - cbd1984 11y ago
    > 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.
- Jtsummers 11y ago
  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.