3 ms·

"but what is wrong with recursion? Why NASA guidelines prescribe to avoid simple technique we were studying as early as in school? The reason for that is static

"but what is wrong with recursion? Why NASA guidelines prescribe to avoid simple technique we were studying as early as in school? The reason for that is static code analyzers NASA use to reduce the chance for error. Recursions make code less predictable for them. JavaScript tools do not have such a precept so what we can take out of this rule?" This is of course, wrong. Javascript has not solved the problem of making recursion easy or sane to analyze. It is quite literally the same problem you have with C. In fact, most javascript tools are way less useful at recursion analysis (IE they produce a much higher rate of false positives) than C tools. "9.The use of pointers should be restricted. Specifically, no more than one level of dereferencing is allowed. Function pointers are not permitted. This is the rule JavaScript developer can not get anything from. " Except that javascript developers use function pointers like they were going out of style ...

wyager 12y ago
I suspect issue isn't that recursion is hard to analyze, but that non-tail-call-optimized recursion has unbounded memory usage. In fact, what makes you say that recursion is difficult to analyze? Inductive proofs over recursive algorithms are generally much nicer than proofs over iterative algorithms.
- bronson 12y ago
  Exactly right. Recursion is the easiest way to blow up the stack (with alloca a distant second). NASA stacks tend to be small, static, and can produce physical harm when damaged. Why avoid recursion entirely? Because it's too easy for another programmer to accidentally convert tail-call optimized recursion into full recursion. That mistake is harder to make on code written as a loop.
- DannyBee 12y ago
  "In fact, what makes you say that recursion is difficult to analyze? Inductive proofs over recursive algorithms are generally much nicer than proofs over iterative algorithms." For static analysis purposes, it is not great. Particularly if it is inside conditionals. Either you eat exponential path blowup (assuming bounded recursion and context-sensitivity) and fix-point it, or collapse the whole call graph cycle starting at the recursion into a single result (which generates false positives). This assumes a single-thread. Concurrent javascript code, with recursion, does not even have a decidable reachability problem, which makes it very difficult to get good answers. Suffice to say, what is easy/hard for humans to prove is not the same as computers. You would have a much harder time getting good static analysis results from a recursive fibonacci function than an iterative one (and this is simple tail recursion)
- jacquesm 12y ago
  You nailed it. Tail calls have constant memory footprints, non-tail-call recursion (assuming the language runtime and/or compiler are able to recognize these situations and convert the tailcall into an adjustment of the variables in scope in the current stack frame followed by a jump). If we'd be worried about our ability to analyze these then we wouldn't be able to optimize away that special case to begin with. I do find that to my imperatively trained eyes it always screams 'stack overflow' at me and then I have to remind myself that will be optimized away. It'd be nice if environments that provide tail call optimizations could be set to fail compilation if any non-tail-call recursion is detected.
  - DannyBee 12y ago
    "If we'd be worried about our ability to analyze these then we wouldn't be able to optimize away that special case to begin with. " Most compilers require you tell them, specifically, that it can tail call everything, before it will do it (i'm talking more about GCC and LLVM here, which are generic compiler frameworks). It will do some tail call optimization, but only fairly basic cases, exactly because it can't analyze what will happen.
pmontra 12y ago
Exactly. I create an array of functions one week ago. Not that it's usual: I had to google how to .call() them :-) Anyway, .call is pretty much used inside many libraries. I just checked the ones in a project I'm working on. It's in jquery, bootstrap, store.js

wyager 12y ago

I suspect issue isn't that recursion is hard to analyze, but that non-tail-call-optimized recursion has unbounded memory usage. In fact, what makes you say that recursion is difficult to analyze? Inductive proofs over recursive algorithms are generally much nicer than proofs over iterative algorithms.

bronson 12y ago
Exactly right. Recursion is the easiest way to blow up the stack (with alloca a distant second). NASA stacks tend to be small, static, and can produce physical harm when damaged. Why avoid recursion entirely? Because it's too easy for another programmer to accidentally convert tail-call optimized recursion into full recursion. That mistake is harder to make on code written as a loop.
DannyBee 12y ago
"In fact, what makes you say that recursion is difficult to analyze? Inductive proofs over recursive algorithms are generally much nicer than proofs over iterative algorithms." For static analysis purposes, it is not great. Particularly if it is inside conditionals. Either you eat exponential path blowup (assuming bounded recursion and context-sensitivity) and fix-point it, or collapse the whole call graph cycle starting at the recursion into a single result (which generates false positives). This assumes a single-thread. Concurrent javascript code, with recursion, does not even have a decidable reachability problem, which makes it very difficult to get good answers. Suffice to say, what is easy/hard for humans to prove is not the same as computers. You would have a much harder time getting good static analysis results from a recursive fibonacci function than an iterative one (and this is simple tail recursion)
jacquesm 12y ago
You nailed it. Tail calls have constant memory footprints, non-tail-call recursion (assuming the language runtime and/or compiler are able to recognize these situations and convert the tailcall into an adjustment of the variables in scope in the current stack frame followed by a jump). If we'd be worried about our ability to analyze these then we wouldn't be able to optimize away that special case to begin with. I do find that to my imperatively trained eyes it always screams 'stack overflow' at me and then I have to remind myself that will be optimized away. It'd be nice if environments that provide tail call optimizations could be set to fail compilation if any non-tail-call recursion is detected.
- DannyBee 12y ago
  "If we'd be worried about our ability to analyze these then we wouldn't be able to optimize away that special case to begin with. " Most compilers require you tell them, specifically, that it can tail call everything, before it will do it (i'm talking more about GCC and LLVM here, which are generic compiler frameworks). It will do some tail call optimization, but only fairly basic cases, exactly because it can't analyze what will happen.

pmontra 12y ago

Exactly. I create an array of functions one week ago. Not that it's usual: I had to google how to .call() them :-) Anyway, .call is pretty much used inside many libraries. I just checked the ones in a project I'm working on. It's in jquery, bootstrap, store.js