Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

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

Tags:

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.

like image 488
MSeifert Avatar asked Jul 14 '18 09:07

MSeifert


People also ask

How do you limit recursion depth?

The “maximum recursion depth exceeded in comparison” error is raised when you try to execute a function that exceeds Python's built in recursion limit. You can fix this error by rewriting your program to use an iterative approach or by increasing the recursion limit in Python.

Does a recursive function always return a value?

All functions - recursive or not - have one or more return . The return may or may not include a value. It is for you to decide when you write the function.

When a method calls itself multiple times it is known as?

In recursion, each function has its own state. So, when the Towers(n-1,fr,spare,to) function runs, it recursively calls itself reducing parameter value by 1 in each call.

How do you stop a recursive function?

A recursive function terminates, if with every recursive call the solution of the problem is downsized and moves towards a base case. A base case is a case, where the problem can be solved without further recursion.


1 Answers

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.

like image 195
MSeifert Avatar answered Oct 11 '22 15:10

MSeifert