Getting around the recursion limit

Get rid of recursion with this trick!

Recursion is great, an extremely useful tool to have a mastery of. However, recursion is limited by the depth of the allowed call-stack before an error is caused. Sometimes, depth is not a problem. But other times, it is better to convert your recursive algorithm into an iterative one by manually managing your own stack, which is what we'll see in this Python video.

SUPPORT ME ⭐
---------------------------------------------------
Sign up on Patreon to get your donor role and early access to videos!

Feeling generous but don't have a Patreon? Donate via PayPal! (No sign up needed.)

Want to donate crypto? Check out the rest of my supported donations on my website!

Top patrons and donors: Jameson, Laura M, Dragos C, Vahnekie, Neel R, Matt R, Johan A, Casey G, Mark M, Mutual Information

BE ACTIVE IN MY COMMUNITY 😄
---------------------------------------------------

CHAPTERS
---------------------------------------------------
0:00 Traversing a tree
2:04 The trick
3:41 More complex example with max depth
5:07 Decoupling

[unusedTV]

You're one of the few channels on YouTube that actually does intermediate to advanced Python content. These are very useful videos with clear, no nonsense explanations.

[mohamedalmahditantaoui]

Love your work, simple and precise. Still waiting for your asynchronous python video.

[AdamHoelscher]

Great example of how to accomplish a Depth First Traversal using iteration instead of recursion. One even better optimization: instead of iterating through `node.children`, we can use `stack.extend`. Readability is about the same, but `extend` will spend more time in C and less in Python, meaning performance is even better.

[PreciousMental]

Thanks this really helped me finish my recursively printing all nodes in a tree while avoid recursion limit homework assignment

[MithicSpirit]

how would you use this on a recursive algorithm where you use the returned value of the recursive call?

[spaghettiking]

Very nice, this might come in handy for me because I'm gonna be writing a compiler, and as part of the translation process I'm having to traverse a syntax tree. I hope the normal recursion will do fine, but in the end it might be more rigorous to do it this way... Enlightening as ever

[royler]

Very nice, would be awesome if we get a video about async in one of the following videos. Maybe add a bit of python3.11 spice to it (regarding syntax).

[lawrencedoliveiro]

My Blendhack module does a kind of brute-force resolution of the types of the loaded memory blocks from a Blender document, by looking at the expected types of the pointers to them. This is a highly recursive process, but I didn’t realize how recursive until I kept hitting Python’s recursion limit. Then when I tried increasing it to quite large numbers, my code would segfault.

So I had no choice but to implement my own stack of blocks currently in the process of being resolved, with the resolution algorithm running as an iterative loop that pushes and pops this stack. My statistics collection indicates that the stack can get as deep as 100, 000 elements.

Blender itself probably doesn’t need to go this deep because it has hard-coded assumptions about the types of the blocks.

[rubykanima]

1:30 I never thought that a sentence like "Thats why the crash happens near 1000 children" would ever be used in a formal manner

[aaronm]

Again, love the content... Somehow also totally unique 👍👍

[maxmarkov]

Liking your videos preventively. Interesting & consistent content

[supermonkeyqwerty]

Lovely! Some of my favourite code is writing parsers for recursive grammars using this style of stacks of arguments / operators :)

[mikhailandronov]

Just stumbled upon your channel, but it's already my favorite python channel ever with tons of wisdom to pick up! Could you please recommend channels like yours but with a focus on PyTorch?

[philstubblefield]

1:06 "...the perfection and elegance that is every line of code beget of your golden fingertips." 🤣 How often have each of us caught ourselves thinking along those lines? 🤔

[hunterwilhelm]

If anyone wants a tail recursion optimization in Python I made a pip package for it. Let me know if you want the link

[urojony]

Ok, but actually this changes the memory complexity from O(h) to O(Δ0+Δ1+...Δh), where h is the height of the tree and Δk is the maximum degree of a vertex on level k of the tree. This is usually not a problem, when the tree is already stored somewhere (if you can store one tree, you probably have the space for another), but what if the tree is too big and it's not possible. Consider the following problem.

In the BigAlpha language, the alphabet consists of d=1000 letters. Anna wants a program that finds some „nice words”. We know that a nice word consists of h=1000 letters and that there is an implemented blackbox function which returns if a given word is nice.

One way to do that is to just make random words and to check if they are nice, but suppose that we don't want to use random numbers. Then we can consider set of all words of length at most 1000 as vertices of a tree. Edge from word X to word Y would exist if Y starts with X and has one letter more. If you use recursion, than you need O(h) memory. If you use the stack implemented in the video, you need O(hd) memory.

It's not like you cannot solve it without recursion. But your code would be more and more similar to the actual recursion. And it's not bad, but it's harder to read. Removing recursion limit seems better. And if you're worrying about eating all the memory and crashing a computer, just add a memory limit.

[lachlanstanding]

that's a great pattern, I will definitely keep that in mind, but I have a question: Have you really solved the recursion limit problem any better than just setting a high limit? Doesn't this approach run the risk of running unbounded, eating up all your memory and crashing your whole computer just like unbounded recursion?

[atrus]

I know Python is your main topic, but do a video. I've never been able to understand this topic fully, and haven't been able to find a resource that explained it well. I feel like you could do a really good job.

[Phaust]

Thanks a lot! Very interesting, as usual! Love dem stacks.

[evlezzz]

If I understand correctly, maximum recursion depth limit is not a safeguard against infinite recursion but a result of C stack underneath python having limited size. So if we set the limit too high (depending on how interpreter has been built) we'd just ruin the interpreter with actual stack overflow from C code.
That being said, in 3.11 a change has been made, and calling one python function from another is not causing usage of C stack anymore, so recursion calls like that bacame safe.