Earlier today I found this post by Ryan Westlund:
Article No Longer Available
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!
Top comments (4)
Interesting!
It looks like in #JavaScript it works with
8925but not with8926Interesting! Also a fun fact is that I tried out a similar method in Python using exec and sting multiply.
But this actually caused it to hit the recursion error earlier than using the method I used in the post. Although it still went deeper than the limit if I remember correctly. Fyi, to not get board I used string multiply and good ol' copy-paste.
But, is it normal to call a magic method?
hehe, no not at all. I just tried to show my thought process when analyzing the problem. The one time I have seen magic methods called directly is when using inheritance:
super().__init__(x, y, z); x,y,z being som parameters to the constructor. Alsolist.__getitem__(my_list, 1)is exactly the same asmy_list.__getitem__(1), this is just passing the parameter self manually to the function. If you want to, you can do this swap with any instance method on any class.