CODEWITHSUNDEEP
c++recursionoptimization
J M
J M

Reputation: 31

Is there a good way to access information outside of a function?

Currently, I am working in C++ on a recursive function that to work, needs to be passed a large array and several constant variables. Here is the structure of the recursion:

void recurse_objects(std::vector<Object> &objects, int i, int j, double merge_distance, double size_enclosure, double timestep){

    //operations performed

    //recursion performed
    if(j+1 < objects.size()){
        recurse_objects(objects, i, j+1, merge_distance, size_enclosure, timestep);
    }else if(i+2 < objects.size()){
        recurse_objects(objects, i+1, i+2, merge_distance, size_enclosure, timestep);
    }

    //more operations performed
}

The function recurses through each unique pair (i, j) of objects. The problem is, at the amount of objects I am working at (500-2000 objects), the function segmentation faults due to the stack filling up - it works for under 350 objects.

It feels like if I could store the array and constant variables somewhere else, I could save room and be able to run computation on those last few objects. Is there a common fix to this problem? The only ones I could think of are using global variables - not feasible since values are dictated by system input, to batch, which would completely kill the efficiency, or just to change the program to a non-recursive one.

Upvotes: 3

Views: 85

Answers (1)

Chris
Chris

Reputation: 36506

If your compiler is not performing tail-call optimization, recursive functions that run too long will always cause a stack overflow. Cutting down the amount of memory stored in each stack frame will delay that inevitable, and let you run it on larger datasets, but they won't remove the problem, since even small stack frames add up.

Your function already appears to be on its way to being tail-recursive, if there are no more operations after the recursive calls.

If you can get rid of those after your recursive call, this will likely come down to what flags you're sending your compiler for optimization.

Upvotes: 2

Related Questions