DEV Community

loading...

TIL: Python Recursion Limit When Accessing Elements in Recursive List

fronkan profile image Fredrik Bengtsson ・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, [...]]
Enter fullscreen mode Exit fullscreen mode

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
Enter fullscreen mode Exit fullscreen mode

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
)
Enter fullscreen mode Exit fullscreen mode

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
Enter fullscreen mode Exit fullscreen mode

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, [...]]
Enter fullscreen mode Exit fullscreen mode

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

>>> my_list[1][1][1][1][1][1]
[1, [...]]
Enter fullscreen mode Exit fullscreen mode

What!?!?

>>> my_list[1][1][1][1][1][1][1][1][1][1][1][1][1][1]
RecursionError: maximum recursion depth exceeded during compilation
Enter fullscreen mode Exit fullscreen mode

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
Enter fullscreen mode Exit fullscreen mode

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!

Discussion (4)

pic
Editor guide
Collapse
gkucmierz profile image
Grzegorz Kućmierz

Interesting!

const arr = [1];
arr.push(arr);

console.log(arr);

It looks like in #JavaScript it works with 8925 but not with 8926

Collapse
fronkan profile image
Fredrik Bengtsson Author

Interesting! Also a fun fact is that I tried out a similar method in Python using exec and sting multiply.

exec("my_list" + "[1]"*10)

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.

Collapse
burdier profile image
Burdier

But, is it normal to call a magic method?

Collapse
fronkan profile image
Fredrik Bengtsson Author

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. Also list.__getitem__(my_list, 1) is exactly the same as my_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.