Fredrik Sjöstrand

TIL: Python Recursion Limit When Accessing Elements in Recursive List

Fredrik Sjöstrand's photo
Fredrik Sjöstrand
·

2 min read

Earlier today I found this post by Ryan Westlund. It reminded me that in Python you add a reference to a list to itself, like this:

>>> my_list = [1]
>>> my_list.append(my_list)
>>> my_list
[1, [...]]
>>> my_list[1]
[1,[...]]
>>> my_list[1][1][1]
[1, [...]]

Sidenote: this is one of the cases where reference counting breaks down and why Python needs a garbage collector (GC). It is the GCs job is to clean up circular references like these. Now, back to the story!

Here we have recursion and in Python, we have a maximum recursion limit. If you have ever forgotten the base case in a recursive function you probably have seen this error:

RecursionError: maximum recursion depth exceeded during compilation

which is triggered when the limit is reached.

How does accessing the elements work? You can give your own classes the []-operator by implementing __getitem__(self, key). So we can probably think about doing this my_list[1][1] as recursive calls to __getitem__:

list.__getitem__(
    list.__getitem__(my_list, 1),
    1
)

It, therefore, seems reasonable that this would trigger the max recursion error if repeated enough times. What is the default maximum recursion limits?

>>> import sys
>>> sys.getrecursionlimit()
1000

Wow, that is more than the times I am willing to write [1] to test my hypothesis. Luckily for us, or at least for me, we can change the recursion limit to let's say 5 using sys.setrecursionlimit. 

>>> sys.setrecursionlimit(5)
>>> my_list[1][1][1][1][1]
[1, [...]]

It must be an off by one error, let's do 6 access instead.

>>> my_list[1][1][1][1][1][1]
[1, [...]]

What!?!?

>>> my_list[1][1][1][1][1][1][1][1][1][1][1][1][1][1]
RecursionError: maximum recursion depth exceeded during compilation

Success!!! So, I found 14 access is what is needed for the maximum recursion error to trigger. Interestingly, I only needed 8 when using exec:

>>> exec("my_list" + "[1]"*8)
RecursionError: maximum recursion depth exceeded during compilation

I'm actually still not sure what causes this behavior. It is demonstrably true that accessing the elements can cause a RecursionError, however, I do not understand why it took 14 access with a recursion limit of 5. Might it be some sort of optimization going on here? Even more interesting is that using exec takes 8 accesses, more than the limit but less than the other method. If you have any idea on what might be causing the behavior, please leave a comment below. It would be really interesting to hear your thoughts on this one!

PythonTIL