Hacker News Reader

Comment by jeffbee | Hacker News Reader

Recursion is one of those things that for some reason they continue to teach kids in college, which has no utility in practice. Things like recursion and linked lists should be erased from the curricula.

There probably is a language and an application where recursion makes sense but C++ isn't one of those languages. Certainly a factorial is a horrible example because iterative is strictly better.

View on HN

I'm guessing that recursion isn't used much in whatever work you do, but it's very helpful for things like parsers, compiler passes, etc. Basically anything that has to walk to tree or directed graph, and where you need to build up context based on the traversal path from the starting point to the node you're currently handling.

Obviously in a non-functional language, you can do these things without recursion by using your own stack rather than the runtime function-call stack. But sometimes it's nice to have the stack provided for you. That also plays well with C++ runtime exception propagation.

In production code, you'd generally avoid recursion to avoid stack overflows.

Given in most languages you can't enforce tail call optimisation, it's risky to use unbounded recursion.

I suspect this guideline varies a lot by industry or by target hardware.

The last time I worked on a project with that rule was about 23 years ago, and that was on a 32-bit system.

Very hard to relate to this perspective. Recursion is extremely useful. It definitely has practical utility, and even in many cases where one shouldn't use recursion in actual code (perhaps because it would risk blowing the stack), it's often much easier to first develop a recursive algorithm and then afterwards create an iterative implementation.

As for linked lists, obviously it's true that the cases where they should be used are much more limited than they used to be. But still, they're a very simple data structure that's easy to reason about and which software engineers are very likely to occasionally encounter in practice. I don't think there's much to be gained by eliminating them from students' education.

Recursion shines when you recurse into many different functions. Function A, B, C, etc. all being called multiple times from each other based on conditions in the data, never returning from the calls. VMs can be like that, also some regex implementations.

Recursion as a concept is useful. In practice, you can sometimes achieve better performance (or avoid exceeding some call stack limit) by doing it "iteratively" in a way that's still conceptually equivalent to recursion, i.e. with a stack you manually manage. I've never had a function call itself in C++, but I've done conceptually recursive things a lot in it.

Manually managing a stack is significantly more expensive compared to utilizing the call stack for recursion. Modern hardware and calling conventions are designed to make call stacks fast.

You should measure this!

For my job involving C++, it doesn't matter which is faster. Just doing whatever is more readable, and since I'm usually doing a DFS/BFS func, it's nice being able to easily toggle that by popping from front vs back. When I'm not, I'd rather have a readable stack trace if something goes wrong and not have to deal with the oddities of recursive lambdas.

In Python, the issue is the easily reachable max recursion depth. Tail recursion isn't optimized.

In Erlang, you use recursion even just to iterate through a list. It's fine, the language is made for that.

My comment was in response to your 'better performance' point. I agree with your other points of course.

I actually +1 on linked lists since it's very cache unfriendly and is actually very niche, but recursion is very solid, specially if your language has tail call elimination

It does depend though, on how the linked list is implemented. If it is backed by an array for example ...

Not sure what sort of code for you write but recursion and linked lists are incredibly helpful.

Why a linked list?

The linked list is a peculiar data structure which makes a lot of sense in the 1970s because all memory reads cost the same and addresses are small, but is terrible in most cases in 2022 because we have huge addresses and very fast local cache. There still are good uses for the linked list, but they're now pretty esoteric.

Using the list concept with recursion is great, but fast implementations of languages in 2022 do not lean on the linked list. Java's ArrayList, and the terribly named C++ std::vector, are more appropriate structures for a lot of cases where a 1970s algorithms book says "list".

Linked lists are probably most common in memory managers, and in embedded programming where memory is very tight, timing is critical, and the cache might be limited. Memory managers use intrusive linked lists to manage the free list; they need a data structure that doesn’t require malloc or new, can grow & shrink dynamically without relocating, and has constant time inserts & deletes from the middle of the list.

Linked lists aren’t very common in desktop application programming, if they ever were, and non-intrusive linked lists as container classes do seem particularly prone to having better alternatives, especially naïve implementations that allocate the list nodes and node content separately. One of the best reasons to reach for a linked list is to avoid all calls to new or malloc or free, so doubling up on them is especially silly.

I don’t think this is really a 70s thing though. Linked lists might have been used slightly more often in the past, but I think they’ve always been used far less than arrays, and my old algorithms books that predate std::vector just use arrays. Maybe the main utility of linked lists is to teach about pointers and algorithm complexity. They do make good examples of pointer management and of algorithms with different big-O than arrays, hashes, trees, etc. I maybe used linked lists a couple of times in games programming, but have rarely ever used them, while they were covered thoroughly in school.

For a conventional malloc-type memory manager I can see this, you don't want to actually walk this list in most cases, you may be concurrent (in which case cache defeating is a feature) and so on.

In embedded my guess would be that you see linked lists because lots of embedded programmers are C programmers and that's what they learned to do, not because it's actually a good choice. I reckon if you look at C programs I wrote in the 1990s there are a lot of linked lists, and I can't defend any of those as the right solution.

Reply on news.ycombinator.com