Python recursion stopped unexpected

Question

Briefly speaking, the recursion stopped halfway though everything else is fine.

The recursion function is shown below (The entire code can be found here):

def DFS(graph, startNode = 0):
    global nodesProcessed; global explored; global finishingTime
    explored[startNode] = True
    currentLeader = startNode

    if startNode in graph:
        for neighbor in graph[startNode]:
            if not explored[neighbor]:
                #checkpoint 1
                DFS(graph, neighbor)
                #checkpoint 2
    else: return currentLeader

    nodesProcessed += 1
    finishingTime[startNode] = nodesProcessed
    return currentLeader

The problem is that after a while's recursion, it stopped. The things that confused me are that:

The input is fixed, but where it stops is not fixed. However, it always stopped at around 7000 times of invoke;
All the failed recursions reaches checkpoint 1 but fails to reach checkpoint 2, and the recursion does not execute at all;
It doesn't reach that maximum recursion time at all, I've set the max recursion as sys.setrecursionlimit(10**6)
It runs pretty well on relatively small input (hundreds or thousands of nodes) but stuck on a large graph which has more than 800,000 nodes.

Which are driving me crazy, I can't see a reason why it doesn't work, no error, no stack overflow, just stopped, saying Press any key to continue ... as if it is finished. Anyone has a clue about what could possibly go wrong?

Recursion can eat up memory in python you might want to make sure you aren't running out. If you run out different things can happen on different operating systems. Linux for example will save itself and Kill the process so as not to crash the operating system. If you are running on Windows or Mac I'm not sure what will happen but it is something to look at. — gabeio
– gabeio, Commented Feb 7, 2018 at 4:40
@gabeio I'm running this on a 16G memory Windows machine, from the task manager, I can see this script takes about 600MB before it stops. But after some tests, it proves that my machine is capable of providing about 10,000 MB for python. So I don't really think it's the memory runs out. — Amarth Gûl
– Amarth Gûl, Commented Feb 7, 2018 at 5:02
By any chance, are you running this on 32 bit Python? As @gabeio mentioned, this could be a memory problem, though if the function terminates and doesn't crash, that seems strange. Could it be some sort of overflow/underflow problem? Can you check the values of startNode/neighbor and see if there is some sort of integer overflow? I don't think you will run into this problem with numbers in the 1e4-1e5 range, but best to check. — Sandeep Dcunha
– Sandeep Dcunha, Commented Feb 7, 2018 at 5:54
@SandeepDcunha I installed python with Anaconda3 64-bit. But the number I'm dealing reached more than 800,000. Also, the recurse always fail to execute when it comes to node 22473 and it's neighbor (or neighbor's neighbor), But because the input is fixed, I'm not sure if that's the problem of the hardware or the problem of the algorithm. — Amarth Gûl
– Amarth Gûl, Commented Feb 7, 2018 at 6:17
Probably unrelated to the problem, but you forgot to return DFS(graph, neighbor) — tobias_k
– tobias_k, Commented Feb 7, 2018 at 16:16

Ante · Accepted Answer · 2018-02-07 16:10:44Z

2

As documentation specifies:

The highest possible limit is platform-dependent. A user may need to set the limit higher when they have a program that requires deep recursion and a platform that supports a higher limit. This should be done with care, because a too-high limit can lead to a crash.

There is a script to check that limit.

You will have to implement non recursive DFS.

answered Feb 7, 2018 at 16:10

Ante

5,4686 gold badges26 silver badges47 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

Amarth Gûl Over a year ago

Well, I found the default recursion limit on my platform is 1000 (using sys.getrecursionlimit()), with the code you provided the bound is about 3900, and my script always stops at around 6700 times of recursion. These number seems a little bit inconsistent. But now I do believe there's something to do recursion bound

Ante Over a year ago

@AmarthGûl Check comment in find_recursion.py module. Last line is "A program that does not use __ methods __ can set a higher limit." Python handles build in functions and operators by calling appropriate methods named with '__'. E.g. to handle a + b, it calls a.__add__(b) if exists, and if not exists than calls b.__radd__(a). It seems to me one operation is implemented by two calls on the stack. First call handles which method to call, second call is to 'real' method.

Collectives™ on Stack Overflow

Python recursion stopped unexpected

1 Answer 1

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related