What is special about a recursive call in a comprehension when the recursion goes very deep?

Question

I noticed that something weird happens when I use a recursion inside a list comprehension. If the recursion goes too deep the interpreter seemingly goes idle (I waited for 5 minutes and nothing happened).

For the sake of this question assume that I want to flatten nested lists (I don't - but it's a short code sample that illustrates the problem I am experiencing):

def flatten(x):
    if isinstance(x, list):
        return [a for i in x for a in flatten(i)]
    else:
        return [x]

With a helper function to create a nested list:

def wrap_in_lists(value, depth):
    a = value
    for _ in range(depth):
        a = [a]
    return a

It works great when using:

>>> flatten(wrap_in_lists(1, 2**10))
[1]

But it completely stops when I use:

>>> flatten(wrap_in_lists(1, 2**11))
# Nothing happens, no exception, no result, no segfault, ...

My question is: What happens/happened here? Why is there no response at all?

---

What is odd is that a similar approach using a generator doesn't show this behavior:

def flatten(l):
    def inner(x):
        for item in x:
            if isinstance(item, list):
                yield from inner(item)
            else:
                yield item
    return list(inner(l))

>>> flatten(wrap_in_lists(1, 2**11))
[1]

>>> # although increasing the depth leads to an recursion error
>>> flatten(wrap_in_lists(1, 2**12))
RecursionError: maximum recursion depth exceeded

If it's important I'm using Python 64bit 3.6.6 on Windows in a jupyter lab.

Answer 1

It's a simple StackOverflow that happens before the recursion limit is reached.

In the second (generator) approach it hit the recursion limit with a depth of 2**12. That means 2**11 should've hit the recursion limit in the first approach. That's because list-comprehensions create an additional stack frame so it's twice the stack frames than the generator solution. The fact that it doesn't throw a RecursionError means that something "fatal" happened to the interpreter (or there is an infinite loop somewhere).

However it's not an infinite loop because if you inspect the jupyter lab responses (for example if you start it from the command line with jupyter lab) you'll notice that shortly after running the flatten(wrap_in_lists(1, 2**11)) line it will print a kernel <xyz> restarted. So it isn't correct that there is no response, the kernel just crashed and the [*] displayed in the jupyter lab cell in this case just means the calculation didn't finish (because of the crash).

That's one of the reasons why you be really really careful if you change Pythons recursion limit or use an interpreter that changed it for you.

Answer 2

I'm not sure why the error is getting silenced in your case. I can't reproduce it here. I tried many values and it either gives error or works.

>>> sys.setrecursionlimit(3000)
>>> flatten(wrap_in_lists(1, 2**10)) #works
[1]
>>> flatten(wrap_in_lists(1, 2**11)) #fails with exception
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  ...
RecursionError: maximum recursion depth exceeded

I'm also using python3 in jupyter notebook.