Fluffy Developer FoxJul 23, 2023

Recursion Wars Episode II: Python strikes back

Because Python does not have real support for recursion (if there is a limit it's not actually supported in my opinion), I had to write this monstrosity to create a list of nested dicts from an object tree.

You'd think that calling dict on the root objects would be enough, but noooo, I have to unfold the trees, break them up into distinct depth levels, then fold everything back up while converting each object one at a time.

#programming #Python

Show threadPup ArlenJul 23, 2023
@FluffyDeveloper it’s disingenuous (nearing misinformation) to say that python doesn’t have real recursion support. Outside of carefully crafted cases to permit tail-chaining, EVERY language has a limited amount of recursion. Every time you recurse, another stack frame has to be added, and that takes memory to do - you’re eventually going to run out. If anything, python’s intentionally limited depth is a lot safer than other implementations that can chew through your systems memory until they wake the OOM killer, which has all sorts of bad consequences. The claims you’re making betray you don’t actually understand how recursion really works or it’s pitfalls - it’s not a good look 😬
Show threadFluffy Developer FoxJul 23, 2023

@puparlen Yeah, too bad that languages like C, Go, Rust, and even JavaScript can effectively recurse a LOT deeper than Python without running into any error :/

A quick test will tell you that Python throws a recursion limit error REGARDLESS of its memory usage, it will do it with an empty function calling itself! I got it to trigger with a whopping 200KB of memory used up XD

And you can still go into overflow before reaching the limit because, again, its arbitrary and independent of memory.

Show threadPup ArlenJul 23, 2023
@FluffyDeveloper but honestly, 99.9% of the time if you’re running into the 1000 limit, it suggests code smell and a time to reevaluate the implementation. Most efficient recursive algorithms use far less depth for reasonable cases. And for what it’s worth, Python is arguably more functional than most languages - internally it inherits a lot of zero-copy and tail-chaining from lisp. Unfortunately as it’s evolved it gets lost in syntax, but comprehensions and generators do use it
Show threadFluffy Developer FoxJul 23, 2023

@puparlen Not really, I tend to write using functional paradigms and recursion is just natural to use when parsing trees. In this case the data comes from a forum-like website so I cannot set an arbitrary limit to the recursion depth. Maybe if I knew that they had one I could use that, but alas that's not the case.

Oh I know that it can do that in the background, it’s what annoys me the most x3

It could SO much more, but its limited on purpose and that's a pity :(

Show threadPup ArlenJul 24, 2023
@FluffyDeveloper I get that your forum gives the appearance of infinite depth. That doesn’t absolve you of needing enough memory and compute to handle your algorithm, and writing it within reasonable limits. What do you do in the circumstance that it has 100,000 depth? Crash? Even your iterative approach will break at some scale - it can’t truly be infinite
Show threadFluffy Developer Fox
@puparlen It's not truly infinite obviously, but a case where you encounter enough comments to crash the memory is not really possible, so you would never reach the crash limit.
Jul 24, 2023 at 12:09amWeb