Python recursive algorithm segmentation fault

Question

I'm pretty bad with recursion as it is, but this algorithm naturally seems like it's best done recursively. Basically, I have a list of all the function calls made in a C program, throughout multiple files. This list is unordered. My recursive algorithm attempts to make a tree of all the functions called, starting from the main method.

This works perfectly fine for smaller programs, but when I tried it out with larger ones I'm getting this error. I read that the issue might be due to me exceeding the cstack limit? Since I already tried raising the recursion limit in python.

Would appreciate some help here, thanks.

functions = set containing a list of function calls and their info, type Function. The data in node is of type Function.

@dataclass
class Function:
    name : str
    file : str
    id : int
    calls : set
....

Here's the algorithm.

    def order_functions(node, functions, defines):
        calls = set()

        # Checking if the called function is user-defined
        for call in node.data.calls:
            if call in defines:
                calls.add(call)

        node.data.calls = calls

        if len(calls) == 0:
            return node

        for call in node.data.calls:
            child = Node(next((f for f in functions if f.name == call), None))
            node.add_child(child)
            Parser.order_functions(child, functions, defines)

        return node

score 1 · Answer 1 · answered Jun 10 '20 at 09:27

If you exceed the predefined limit on the call stack size, the best idea probably is to rewrite an iterative version of your program. If you have no idea on how deeply your recursion will go, then don't use recursion.

More information here, and maybe if you need to implement an iterative version you can get inspiration from this post.

The main information here is that python doesn't perform any tail recursion elimination. Therefore recursive functions will never work with inputs that have an unknown/unbounded hierarchical structure.

Python recursive algorithm segmentation fault

1 Answers1