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!
Latest comments (4)
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.Interesting!
It looks like in #JavaScript it works with
8925
but not with8926
Interesting! 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.