Hacker News Reader

Comment by Naac | Hacker News Reader

Could recursion be ( one of ) the reasons why ML and Scheme ( and lisp, clojure, etc. ) aren't popular as industry languages?

I learned recursion in University, it's undeniably a foundational piece of Computer Science theory. I use recursion when I have to do interview problems. And I think that's about it.

The number of times I actually used recursion in production was maybe twice. And one of those times the PR was rejected. In my experience the overhead of understanding the code outweighs its terseness. This is also how I sometimes feel about macros in clojure. The cons outweigh the pros.

View on HN

Have you ever

- Traversed a directory hierarchy to compute the total size or other statistics about its contents?

- Searched for a DOM element on a web page matching certain criteria without using third-party libraries or helper functions like querySelector()?

- Implemented a hierarchical navigation structure in a user interface?

- Work on parts of a compiler/interpreter or other code that has to deal with formal language?

- Written a parser for a file format that contains arbitrarily nested data structures (e.g. HTML/JSON)?

- Done anything with trees?

- Solved a problem by breaking it down into smaller versions of the same problem, solving those, and then combining the results?

I know that for lots of programming tasks recursion is not needed, but I'm genuinely curious as to what kind of software you work on where you've never encountered a problem that requires a recursive solution?

I've been working mostly in the payments domain for the last 16 years. 90% backend, 10% web frontend.

So far, I've had write recursive code just once to convert SOAP requests/response to REST request/response on the fly so that the test cases that were written using SOAP client could be reused to test REST end point as well.

To state the obvious, the chances of encountering recursive code depends on the domain. In my experience though a typical CRUD business app won't require a recursion as you pointed out. The examples you sited are mostly encountered in a "framework" code (e.g., Spring, some UI framework) and as is typically the case the number of developers "using" a framework is an order of magnitude more than those who implement/maintain them. Same is the case with compiler. On the other hand, those who deal with the lower level system code (OS Kernel, RTOS etc.,) shun recursion altogether to avoid its unpredictable stack need. So in the spectrum of developers the band of coders who frequently deal with or encounter recursion is quite narrow IMO.

There are languages where recursion is the only construct available to deal with a collection of values so for those programmers recursive technique is a muscle memory. But I suspect there aren't as many professional users of such languages.

None of the above actually require recursion.

Some of the above problems have very neat recursive solution but the recursion is bad idea as it tends to various edge cases.

For example, "write a parser for a file format that contains arbitarily nested data strucutres", is exactly a problem where you DO NOT want to use recursion, and the reason is that "arbitarily" part. What if there is 1000 levels? What if there is 100 thousand levels?

DoS guys love these kinds of implementations. Just send very small, very well compressed payload and look how it all crashes and burns.

You’d run into the same denial of service problem in an iterative solution with an explicit stack/data structure that can be grown arbitrarily as well. The only way to prevent such an attack is an explicit limit (perhaps calculated at run time based on system specs) which can be done with either a recursive or iterative implementation but requires deliberate awareness either way.

Fair point, but how frequently do you see recursive implementations that also pass information to track recursion depth and various other information to limit resource usage?

Have you ever seen a recursive call that also tries to detect/break cycles in the data structure?

I suspect the reason these things get left out the moment the developer decides on a recursive function is because it doesn't look nearly as much elegant then.

Depth is just an extra parameter d, which you pass to the recursive calls as d + 1. This is still elegant compared to tracking depth in a non-recursive solution.

When you add this parameter to a recursive solution that is lacking it, your compiler will flag all the places where you are neglecting to pass it, and you just copy and paste d + 1 into those places. Or at worst, it will be caught as a run-ime insufficient parameters error.

At the end of this exercise, you not only have working code, but an inductive proof that d has the correct value everywhere. There are no cases where the depth is mismanaged, as could happen in some iterative solution where you must insert assignments to d, that do not create any sort of error when they are missing.

:(){ :|:& };:

Recursion doesn't use more space than iteration in languages with tail call optimization

That's false.

You would be correct if you wrote "Tail-optimizable recursion doesn't use more space than iteration in languages with tail call optimization"

You're right, that's what I meant.

I would say, DoS people love these kinds of specifications.

I would specify the data structure is ostensibly arbitrary, but conforming implementations can diagnose and reject more than 64 levels of nesting.

Anything needing more than 64 levels of nesting can safely be assumed to be DoS.

> I know that for lots of programming tasks recursion is not needed, but I'm genuinely curious as to what kind of software you work on where you've never encountered a problem that requires a recursive solution?

There are no problems that require recursion, since recursion and iteration are equivalent. You can do all of the things you list with a while loop plus state variables.

Recursion (especially in languages with pattern matching and other features common in the same set of languages in which recursion is more idiomatically favored) can provided solutions that are simultaneously more clear and more terse, but it doesn't expand the set of solvable problems.

Let's improve peterkelly's question. How about:

I'm genuinely curious as to what kind of software you work on where you've never encountered a problem where a while loop required an ad hoc dynamic stack to track state, and so never had to consider the possibility of recursion as a viable, attractive alternative to that.

Using a stack-based data structure of your own is always better than using a call stack for recursive traversal:

- You get to store only the state you strictly need and no more. A call stack stores all local variables and parameters for each frame, potentially wasting memory.

- You get to access previous elements. A call stack does not typically allow you to access data in previous stack frames.

- You get to push/pop multiple, variable number of elements per iteration. Call stacks typically only work with a fixed number of local variables/parameters per stack frame. The workarounds are to 1. dynamically allocate memory for each traversal, which causes lots of fragmentation, or 2. use an oversized fixed buffer for each stack frame, which causes memory waste, or 3. use an ‘alloca’-like construct, if your runtime supports it at all.

- You get to explicitly bound its memory usage and use custom handling/error reporting when your desired max depth is exceeded. Doing so with a call stack is typically a lot more clunky and bug-prone, as it requires exception handling and mutating global state.

- You can serialize/deserialize your stack to/from persistent storage however you like if you wish to pause traversal and resume it later. A call stack can only do this if it’s a ‘stackful coroutine’, which even if it is supported in your runtime of choice, gives you little to no control over where or how it is stored.

Never once had to do any of those in a professional setting. Mostly just creating reading, updating, and deleted database records with a very simple UI (if any at all).

I have used recursion, particularly due to my love for Erlang, just not in any software someone paid me to work on.

There are problems that are inherently tree-structured and where anything other than recursion feels wrong.

“Process all the files in this directory structure, counting them and summing their size.” Sure, you can solve that without recursing, but I’d trust a recursive algorithm to have fewer hidden bugs.

At least the recursive version stops by blowing the control stack when there is a loop in the file system.

IMO vaguely, lisps and ml are disqualified way earlier.

Lisps don't even pass the syntax phase.. newcomers won't have the tool-magic dopamine hook (say the first time you saw PHP map syntax, or ruby blocks or c# interop features). That's what people love at first, it gives a sense of a large new universe of powers.. while lisp is a naked white page of parens.. people just don't see what it's for. Other people will click on the deeper uniformity and lack of syntax as a lever.

Same goes for fp.. people see a soup of function, it's meaningless. Again the syntax hook is strong and instead of having f . g . h you get @f.then(g)[[h]] the brain gets tickled differently.

> newcomers won't have the tool-magic dopamine hook

How C wasted the Pascal family languages in the 1980's.

In 2020 I wrote a serialization system for types in C, as the foundation for a kind of distributed database. Types are a tree structure: records with fields that can be records; arrays with elements that can be any type. Thus the serializing and deserializing operations are recursive.

The system has no external tooling (no description language). The application uses the C API to construct the needed types at initialization time.

I have a test case whereby a whole linked list is serialized and deserialized. The deserialize function mallocs the necessary nodes. There is a function to recursively free the object, using the serial type as a guide.

Another time, a little bit farther back, I worked with something recursive on the job fairly recently was speeding up the recursive file system tree walking function in BusyBox. It fails to take advantage of the Linux-specific d_type field in the inode. With that you can avoid stat calls.

This shaved a bunch of time off the boot of an embedded system, where BuxyBox's mdev program was scanning through device nodes in /sys.

Yet another time. I used recursion to shrink a Linux image by blowing away unused content in the initramfs. That time I used Python to write a kind of "garbage collection" program: it recursively traversed the contents of an initramfs filesystem, determining what files are reachable, marking those files and deleting the rest. Reachability was determined mainly by scanning the file contents for occurrences of the names of other files, with some other heuristics. The root node was the init script; the idea being that anything not required by the initramfs init script is bloat. The idea worked; we got a smaller initramfs that still booted fine.

Yeah, every time I've written I recursive algorithm in the past, I've eventually had to come back and reimplement it as iterative. It's such that I no longer start the recursive approach anymore and go straight to iterative.

The iterative solution is better in every regard. The state transitions are easier to see, and the sub procedures are easier to identify and split up, if necessary.

I have a degree in Computer Science, I did extremely well in that degree program, and I understand algorithms very well. I don't get the fascination with recursion in CS theory. It's just hiding state on the stack frame. That's why it's such a terrible tool, not just for engineering, but for teaching as well. Every recursive solution has an iterative solution, even if it's just tossing your state into a Stack data structure you manage yourself on the heap. You'd think you'd want to call that out for students.

I only use recursion where it makes sense and I can guarantee O(log n) runs. Unbalanced tree? Iterate. Large graph? BFS. That said, I agree with another comment here that you're more likely to have a bug code where you're maintaining a stack by hand. Recursion is easier when it's the best fit for the problem.

Fundamentally disagree. Any bugs in the iterative approach are likely to be found during development on even the simplest of synthetic test data sets. But the recursive approach has a gigantic bug lying in wait for you to run more data than you originally anticipated: the stack overflow.

I used to proctor an on-site laptop coding test where part of the solution involved traversing a large digraph. Maybe 50% of candidates could do it on their own without a bug in 45 minutes. 15% of candidates knocked it out by the halfway mark. Not that this is the best use of recursion--both implementations still need to track visited nodes.

The Forth is not strong with this one... (I am fully on your side btw)

ColorForth mostly forces you to use recursion for loops

Some languages don’t have loops but rather have very good tail-recursive semantics. In that case, nothing is hiding in the stack.

Talking about loops vs recursion is interesting but it feels kinda like salt vs pepper to me. I like both and use both where appropriate.

While we are on the topic of similarly misused constructs, .stream() pipelines in Java are often clear and concise but as they get longer and hide more stuff in the stream, a loop would make far more sense and provide a much smaller runtime complexity.

Often, people will aspire to create “beautiful” code where they relate recursion/loops/streams/etc as something beautiful. In that vein, I don’t really care if code is “ugly” but I do care if it’s unmaintainable, needlessly slow or accidentally complex.

Yeah, one of my last favorite phrases is "elegant code". "Elegance" is an attribute I'd assign to a dinner party, not work.

Math heads frequently use the term for proofs. I see it as carry over

I use recursion fairly often, and I almost never come back and reimplement it as iterative.

Mostly because I know my data structures are bounded, and the thing I'm writing isn't terribly performance sensitive.

The iterative solution is in the language we use a lot more verbose. I'd have to create a separate type to hold any parameters if there's more than one and I'd have to make my own stack of that type. So for most things I just go for plain old recursion.

Probably the other PR just slipped through... What I find difficult with recursion in practice is that the stack depth is quite limited, also depending from what stack depth you are calling the function. Of course memory can also blowup but this is easier to reason (and adding 128gig might just solve it)

Stack-depth is an implementation detail.

It's chicken-and-egg. Programmers think of recursion as that thing that blows up the stack, so they don't demand that language implementers do a better job with it. Language implementers don't stop recursion from blowing up the stack because no-one is asking them to do so.

Yes. So you cannot use it in production.

Maybe, but I don't see it as "recursion is hard," I see it as lisps being more clever than pragmatic.

At least Common Lisp, Racket, and Clojure seem more pragmatic than clever to me. How are they "more clever than pragmatic" in your opinion?

Reply on news.ycombinator.com