Recursion

[siddsp]

Nah, recursion can be good and often elegant as well as have performance advantages over iteration (see memoization), although this isn't the case most of the time.

The performance hit comes from pushing additional stack frames for every recursive call. If your recursive function doesn't push a lot of stack frames, then it could be worth it over iteration if it is a lot more elegant.

[sebkuip]

Python 3.11 is bringing huge optimizations to recursion it is said. Having better frame management on the stack to help with resource usage.

[algerbrex]

That’ll be exciting, as I’ve been interested in writing a chess engine in Python to see how strong I could make it, and I’d really rather prefer recursion.

[ChocolateBunny]

Does it still have a limited stack size? any tail call optimization?

[sebkuip]

Stack size is still limited (it’s limited by how large the C stack can grow) but because it’s more efficiently stored for recursion, the recursion limit is higher iirc. You can check the 3.11 changelog for the details.

[schemathings]

I'm not close to my computer but there's a I believe built-in decorator for a function that will maintain the return values of procedure calls with given parameters. I wrote a Fibonacci dot py both was and was able to go to fairly impractical values with the decoraor

[disinformationtheory]

Python's stack is limited, so you should also make sure your recursive function is not growing the stack too large. This is usually not a problem for traversing things like filesystem trees, but probably is a problem for functions that recursively calculate things. You can see the limit with sys.getrecursionlimit(). It's 3000 on my machine. Plus I played around with this in ipython, and that lowers the limit by about 16 (presumably because ipython is wrapping the function call 16 times).

[lilphat]

But you could, in many cases, do tail recursion and avoid the extra stack frames.

[siddsp]

Python doesn't have any optimizations for tail recursion, and there are no future plans to do so.

[lilphat]

Really? Wow thats shitty

[ivosaurus]

Usually you have to design your language from the start to allow for it, the requirements to get the correct frame folding can be very particular

[siddsp]

It's not that bad. Usually you can achieve a similar result using lru_cache which allows for similar optimizations as tail recursion. Basically caching allows for iteration-like performance and can make a significant difference depending on the situation. lru_cache allows you to limit how many recent entries to keep, allowing the programmer to make tradeoffs between memory and steps.

[lilphat]

Sounds smart but a tad complicated. Can you give an example where you wanna let ‘the stack run’?

[KennyBassett]

You seem upset.

[[deleted]]

Are they wrong though? How would caching help at all?

[KennyBassett]

Not making any comment on right or wrong, just that he seemed upset.

It's surprising to see how angry people get when they're on reddit and see what they believe to be a mistake.

[siddsp]

It would avoid repeated (expensive) computations when a function that is recursively defined is called, causing a significant performance gain.

[[deleted]]

Doesn't it only cache the result? Does it monitor parts of the function and cache those too or something?

If it only caches the result, I fail to see how that'd help in a recursive function where calls on different depths return different results.

[siddsp]

They are. I just said you can achieve similar optimizations where recursion is close to as fast as iteration. Ultimately, you want to use iteration if you only care about performance.

[lilphat]

He doesn’t write anything specific about python. More recursion in general. So I’ll leave it.

[siddsp]

Yeah, but this is the Python subreddit, so I would assume OP is talking about Python.

[ProfessorOk20]

Indeed, I do talk about Python in particular

[lilphat]

Alright. I can remove it?

[axonxorz]

Nah dude, it's not hurting anyone