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’m piecing together the details from your posts and I suspect it’s something to do with the yields in your __iter__ (I’m not 100% on that, just tracing very roughly). Those calls will retain the containing stack frame so they can resume; if your recursion touches that callback your stack depth would balloon. Even just a small retention (the one or two extra you mentioned) would cause problems pretty quickly
Show threadFluffy Developer FoxJul 24, 2023
@puparlen That was my exact thought. I am actually planning on getting rid of the __iter__ method and just add an as_dict() one instead that doesn't use yield. Not as pretty but much safer.
Show threadPup ArlenJul 24, 2023
@FluffyDeveloper dataclass? https://docs.python.org/3/library/dataclasses.html. as_dict out of the box and nice efficiency from __slots__
dataclasses — Data Classes

Source code: Lib/dataclasses.py This module provides a decorator and functions for automatically adding generated special methods such as__init__() and__repr__() to user-defined classes. It was ori...

Python documentation
Show threadFluffy Developer FoxJul 24, 2023
@puparlen That was my first implementation, but I didn’t feel it suitable for “interactive” objects. Controlling the __init__ is quite annoying, and because I use recursive and looping references, I'd have to change so many methods that I might as well create a manual class :(
Show threadPup Arlen
@FluffyDeveloper fair. I run into this a fair amount myself. They’re handy for some things but yeah, cumbersome quickly. Nothing wrong with manual classes :3
Jul 24, 2023 at 12:26amWeb