4 ms·

> 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 g

by 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.

by cbd1984 11y ago

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.