It is interesting that recursion is still considered to be so novel on blogs and forums. From what I have seen of current CS curriculums, recursion is usually taught in the first year immediately after introductory CS. It is almost impossible not to use recursion when dealing with tree structures (using an explicit stack takes a lot more code, most coding interviews don't ask for an iterative solution unless absolute…
After 20 years of software development in a variety of languages and projects, I've come to the opinion that recursion really should be relegated to being a novelty. Few languages offer tail-call optimization. If we look at popularity of languages, then the likelihood any particular solution is going to end up in such a language is vanishingly small. For the remaining languages, fitting into the stack depth is easy t…
I don't know if you mean that literally or just as a rhetorical exaggeration, but it's absolutely false. The first example that came to mind is Quick Sort, search for the iterative version of the algorithm and compare it with the traditional recursive version, easily a 10x factor. The increase in complexity isn't linear in code size either, the code that replaces the simple recursive calls is full to the brim with loops, state and conditional mutations, i.e. Free Bugs, yummy yummy.
>Few languages offer tail-call optimization.
I was hacking on a (non-tail-) recursive solution to a problem a couple of days ago in a repl.it container, and a buggy solution exploded after consuming 15000 stack frames. The repl had 1024 MB RAM as a max limit. The point is, absence of tail cail optimization is rarely if ever a real problem in a language that has loops, its a big, big problem if the language doesn't have loops, but as long as the language has loops and relegates recursion to the "Side Role" its so good at, its just not that of a big deal.
This also fails to consider why recursion is such an attractive algorithmic construct, tail recursion is absolutely trivial, it can be transformed to loops mechanically, it rarely adds anything of value to the readability and expressiveness of code.
The vast majority of interesting and useful uses of recursion is the non-tail-recursive variety, where you have to use a stack anyway, at this point the whole argument reduces to whether you can maintain a stack more efficiently and readably than the machine, which in my view ends in you losing to the machine 9 times out of 10.
>And frankly, lots of programmers don't have a good handle on it, even the ones who studied CS in college, so asking them to maintain recursive code written by someone else usually ends pretty poorly.
If those programmers were asked to instead maintain the explicitly iterative version of the code, I bet it would end even more badly. Recursion, after the initial cost of watching a few tutorials, is less confusing than loops. It's about hiding state, how on earth is explicitly managing all that state yourself better? This is like saying that "2+46/(3+1)4" is best calculated as a long sequence of 2-argument assembly instructions because its more explicit that way, its more explicit, true, but - paradoxically - way more obscure.
>Many safety regulations covering vehicles from cars to spacecraft explicitly ban recursion because of these issues.
Embedded Systems safety regulations and conventions ban a lot of things, recursion is not special at all. One thing is dynamic allocation, another thing is multiple returns out of a subroutine. Are you ready to give up those 2 things?
It makes no sense to take the conventions of a very specific and idiosyncratic industry like that and try to derive from it universal rules that should govern all software.