[melony]

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 absolutely necessary).

[moron4hire]

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 to get wrong. It's easy to end up in an infinite loop that ends in an obscure error with a confusing, verbose, needle-in-hay-stack stack frame that over complicates debugging. 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.

So when we consider that, actually, no, it's not true that using an explicit stack takes "a lot more code" (it's like, three extra lines), recursion starts to look more and more like a code smell, a smell indicating the originating programmer is more a temporarily-embarrassed mathematician than an engineer.

To be clear, I have no problems conceiving of and implementing recursive solutions to problems. But every single one of my recursive solutions has eventually failed to survive contact with real life data. It might be next week when the code goes to production or it might be a year from now when the data processing needs grow, but I've eventually replaced them all.

I'm not the only one with this opinion. Many safety regulations covering vehicles from cars to spacecraft explicitly ban recursion because of these issues. We need to just stop with the fetishising of math in software development.

[soegaard]

It's great to have support for tail recursion when implementing recursive solutions, but it is a tall order to add to more traditional languages. However tail recursion is not the only trick Racket has up its sleeve.

In Racket you can't get a stack overflow.

At the time a potential stack overflow is detected, the oldest parts of the current stack is copied to the heap and a fresh stack is introduced. When the stack underflows the saved stack is reinstated. [At least this is a rough idea of how it works - implementation details differ to make it process efficient.]

This means that you can rely on recursive solutions even when the recursive call occurs in a non-tail context.

This idea (no stack overflows) could be used in more traditional languages too. As you write in traditional languages there is a real risk to bump into the stack limit.

[throwamon]

Sounds very good, but you make it sound like there are no considerable downsides. Why aren't more languages doing it?

[soegaard]

Beats me.

[dgb23]

In web/gui programming it’s a good fit. Your data is a tree that you render on a screen, so it’s by default relatively shallow and not very big. It’s never going to blow the stack and the benefit of using recursion, closures and functional composition is you get clear, dense code and tend to make fatter data structures and more general code.

[nonameiguess]

Yep. Same thing with filesystems. Since they're meant for humans to traverse, finding a directory structure with deep enough nesting to blow up the process stack or hit a runtime recursion limit is sufficiently rare that you shouldn't even worry about it. I'm sure there are plenty of other examples where the practical limit you'll see in much lower than what an address space stack can fit. We had a task at an old job to create dependency and build trees of every service in the overall project and then operate on them. Even assuming a language runtime with a very small limit, say Python with its 997 or so default maximum simultaneous stack frames, we didn't have 997 individual services, so even the maximally malicious dependency tree couldn't have exceeded that limit.

[908B64B197]

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

Honestly that speaks to the caliber of programmers at play here. Sure, the average bootcamp grad probably can’t use a recursive function, but a real software engineer should have mastered it during any serious intro class. Without recursion I’m not sure how we would even be programming (think of all the parsers and grammars relying on it!).

> So when we consider that, actually, no, it's not true that using an explicit stack takes "a lot more code" (it's like, three extra lines), recursion starts to look more and more like a code smell, a smell indicating the originating programmer is more a temporarily-embarrassed mathematician than an engineer.

It sure is a code smell if the average programmer in a given org can’t understand it.

[Banana699]

>it's not true that using an explicit stack takes "a lot more code" (it's like, three extra lines)

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.

[BeetleB]

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

Indeed. On one automotive project, we could not use C++ strings, due to the hidden dynamic allocation.

[Gollapalli]

Do you have a source for the embedded systems safety regulations bit? I was under the impression that governments had neither insight nor competence to decide such matters.

[Banana699]

The regulation I was thinking of is MISRA[1], a very popular piece of convention that is used and referenced in, among other things, the JSF program (F-35 fighter airplane), the Jet Propulsion Laboratory (NASA), and AutoSar (another standard for embedded system in automotives).

From [2] (2012 version) (warning : annoying ads and misleading download button takes you to registration, but it's the only free source I could find with detailed rationale in each rule) :

Rule 15.5 : A function shall have a single point of exit at the end

Rule 21.3 : Memory allocation and deallocation functions of <stdlib.h> shall not be used.

From [3] (2004 version) (pdf) :

Rule 14.7 : [Same as Rule 15.5 of [2]]

Rule 20.4 : Dynamic heap allocations shall not be used

[3] is a pdf containing the 2004 version of the conventions, but no rationale is given for each rule.

>governments had neither insight nor competence to decide such matters.

On the contrary, things like banks, medical devices, aerospace and defense are heavily regulated by the government, source code is just another component in the whole system, why shouldn't it be regulated like hardware ?

As for competence, the government is not all bureaucrats and officials, they can hire specialists to do their inspections.

[1] https://en.m.wikipedia.org/wiki/MISRA_C

[2] https://www.academia.edu/40301277/MISRA_C_2_012_Guidelines_f...

[3]https://www.google.com/url?sa=t&source=web&rct=j&url=https:/...

[CraigJPerry]

And your non-recursive solution will usually be faster too.

It Will usually offer simpler opportunities to parallelise too.