Take a look at the wikipedia page for computing Levenshtein distance: https://en.wikipedia.org/wiki/Levenshtein_distance#Computing...
The recursive version needs barely any explanation. But ask me to carry it out by hand and I'm sure I'll pretty quickly get lost. The iterative version needs a lot more explanation for why it is the way it is, but I also think I could carry it out on paper quite easily.
What’s complicated about a recursion?
> If you see problems, its because something is modifying it between runs, but that wasn't a fault of the iterative strategy, it was the fault of a bad programmer.
> Conversely, you must always make sure the stopping condition and all base cases are met during recursion.
You seem to be applying a double standard here.
> Forget one corner base case and you got a rare production bug.
Base cases are usually much easier to reason about.
> What’s complicated about a recursion?
Especially as iteration is just a special case of recursion :)
How about unknown potential stack size?
How about factoring a large number with recursion?
Everything recursive can be transformed to iterative and yea sometimes it’s not as sexy but neither is a helmet
https://www.reddit.com/r/programming/comments/3dnsh1/nasas_t...
They also proscribe unbounded iterations (point 2). In any case, NASA’s guidelines for mission-critical code are not necessarily good guidelines for general software engineering, given the constraints involved.
It’s also worth noting that recursive solutions are probably more amenable to static analysis and automated theorem proving.
> How about unknown potential stack size?
If stack size is a problem, try an iterative solution.
> How about factoring a large number with recursion?
Go with iteration.
You keep editing your answer to add more cases where iteration is the way to go. I’m not disputing there are use cases where iteration is appropriate.
More like they're using an old Fortran 77 environment which doesn't support recursive functions.
NASA's rules, the ones being referenced above, are designed for safety. They require code to be easy to statically analyze and to have absolutely predictable behavior.
Also to be avoided: memory allocation, unbounded loops, function pointers, preprocessor macros.
https://en.wikipedia.org/wiki/The_Power_of_10:_Rules_for_Dev...
This is in addition to not using recursive functions being pretty standard in anything embedded. Early computers and embedded systems had very limited stack space or had calling conventions that made recursion impossible.
The rationale they used for these rules was written down. It has nothing to do with Fortran. I've offered links that you can read. You're making more assumptions. If there's C-to-Fortran calling at all, then recursion presents zero extra difficulty. Once you can make any function call, you can make all function calls.
> This is in addition to not using recursive functions being pretty standard in anything embedded.
It's true that for small embedded devices, recursion is not used often. It's also true that function pointers and heap allocations and unbounded loops are generally avoided too. Though, often main() in an embed is a white(true){} loop. I wouldn't be surprised to see that at NASA.
One could argue that all of these 10 NASA rules represent some standard practice in embedded code and/or some degree of common sense. They're not claiming to be new or non-standard or unintuitive or innovative; they simply wrote down what people agreed are best practices.
"Give all loops a fixed upper bound. It must be trivially possible for a checking tool to prove statically that the loop cannot exceed a preset upper bound on the number of iterations. If a tool cannot prove the loop bound statically, the rule is considered violated."
https://pdfs.semanticscholar.org/ad40/26510beb1a309902704583...
This isn't just a NASA thing. Pretty much any embedded coding standard says the same thing. The JSF C++ standard, and MISRA-C I know both do as well, just off the top of my head.
That's a really good trade-off for them but it does not necessarily help readability.
You shouldn't have to know about the implementation when writing portable code. If you introduce recursion, you now need to worry about implementation since the machine max stack size is now an issue and you've broken the abstraction. And what exactly did you gain that outweigh's the cons?
You started with the assertion iterative implementations were more intuitive and easier to read so this is a bit of goalpoast-moving. Write an iterative pseudocode DFS or quicksort. How 'intuitive' does that look?
" I'm willing to bet most people if shown 10 recursive and 10 iterative solutions to the same problems would admit the iterative approach is more intuitive. "
Now you are at NASA sending probes to asteroid Weasel 39812.
If a recursive solution works on a small input, it will work on a big input. If you missed a base case, you'll see it immediately because trivial (literally!) input will make your solution fail to terminate.
In production, the main problem with recursion is stack size limits (or more generally memory limits) if you can't/don't use tail-call elimination.
If you are working on any kind of tree structure, graph, parse tree, etc., recursion can be really beautiful and clear.
My theory: folks like iteration because 90% of the "for" loops they write are really just "foreach".
I didn't understand this comment. What do you mean by "for vs foreach."? Can you elaborate?
If you need to return values for processing each child, and integrate them at the parent, then your solution gets tougher to reason about, as there's an ordering constraint and a dependency.
Recursion doesn't come up super often in most domains, but it's not rare. E.g. doing anything non-trivial with the DOM in a web front end, parsing an XML or JSON document, etc.
So, intuitive is not so valuable unless you get correctness out of it.