function stack overflow when 5000+ deep recursion

Question

This function works fine with smaller arrays. But, when, given very large array of "int"s it fails miserably. I looked up and found out its the stack that is out of memory which was causing the problem because it can't allocate enough space to hold all of the inner loop's variables. So how to work around this?

void subsetSums(vector<int> arr, int l, int r, int sum=0) { 
    if(l > r){
        cout << sum << ", ";
        return;
    }
    subsetSums(arr, l+1, r, sum+arr[l]);
    subsetSums(arr, l+1, r, sum);

}
    int main(){
    vector<int> arr(500000, 1);
    subsetSums(arr, 0, arr.size()-1);
    return 0;
}

I just want to "hot fix" this for now. Then, maybe I will find optimal solution to this problem.

As it is stack overflow, you can workaround it by enlarging stack size which is depend on your OS. — Hanjoung Lee, Jul 23 '19 at 03:51
One very quick patch would be to change the first parameter to `std::vector const &arr` which might save a few bytes each time as you're just pushing a single reference (or it might even get optimised away!) instead of a whole `std::vector` control structure. — Ken Y-N, Jul 23 '19 at 03:52
Are you required to use a recursive function? A stack of depth 500,000 does not sound like a good idea to me. — R Sahu, Jul 23 '19 at 03:56
no but i can't really figure out any other way to make a function that checks sum of all combinations of elements — , Jul 23 '19 at 03:59
@Sari, my suggestion would be to state the problem you are trying to solve. I am sure you will get some useful suggestions/answers to that. — R Sahu, Jul 23 '19 at 04:01
its here https://www.careercup.com/question?id=5164935710507008 — , Jul 23 '19 at 04:06
Remember, recursion works by placing the current state on a stack then repeating with a new input and further stack pushes. AFAIK any recursive function can be made non recursive by simply storing your "stack state" on... your own stack! At least thats a good way to start un-recusing it. — ug_, Jul 23 '19 at 04:16
Your bigger problem is that this program will print 2^500000 values. The universe will end before this program finishes. — Raymond Chen, Jul 23 '19 at 04:30
@RaymondChen when I find the solution it will just return some value and wont print anything. — , Jul 23 '19 at 04:51
Raymond's point is about the time complexity of your algorithm, and nothing to do with whether or not it actually it prints anything. — paddy, Jul 23 '19 at 05:11

Sami Sallinen · Answer 1 · 2019-07-23T04:47:41.790

0

You can do three different things:

Reduce stack usage

Instead of passing a copy of the vector and 'r' for each function call, when they dont change at all, you can make a structure that has these as members and pass a reference to the structure as a parameter. If you are not afraid of global variables, you can make these variables global and not pass them as function parameters, although the style police may come to take you away in that case.

Also on some compilers, the non-optimized or debug build will use more stack, so try the release build target or turn on optimizations.

Increase stack size

The way to do this depends on the compiler and the platform. Here is how to do it using gcc and linux: Change stack size for a C++ application in Linux during compilation with GNU compiler

Change to a non-recursive algorithm

Often there is a faster, and more memory efficient algorithm for doing the same thing as the recursive one. In this case it is obvious. This is usually the thing to do in real-world production code.

edited Jul 23 '19 at 04:47

answered Jul 23 '19 at 03:59

Sami Sallinen

3,203
12
16

1) did not work. 2) i will try. 3) my brain is in pain – Jul 23 '19 at 04:02
Edited the answer for 1. The general idea is a way to find opportunities to reduce the number of parameters passed on the stack. – Sami Sallinen Jul 23 '19 at 04:15
A non-recursive algorithm that can compute the sum of any subset in constant time is pretty easy to write. It just requires a pre-pass over the vector to compute the cumulative sums: `std::vector cumsum; cumsum.reserve(arr.size()+1); cumsum.push_back(0); for(int x : arr) cumsum.push_back(cumsum.back() + x);` -- now you can use that to compute the sum between any two positions as: `int sum = cumsum[r+1] - cumsum[l];` – paddy Jul 23 '19 at 04:34
@paddy I meant ALL POSSIBLE SUMS. take this for example [1, 3, 7, 10, 100] your example wont do this combination 1 + 100 or any two points without the numbers between them – Jul 23 '19 at 04:55
1

Sure it can. Just take the sum of range 1:5 and then subtract the sum of range 2:3. If you are really wishing to precalculate every conceivable sum, then Raymond Chen has already pointed out the absurd time complexity of this. Essentially, the decision about whether or not to include a number in the sum can be considered as a single bit for that position in the array. And so the total number of sums is 2^500000 -- this is not computable. If you think you need this, then perhaps you misunderstand the problem you're solving, or your approach is invalid. – paddy Jul 23 '19 at 05:21
@paddy I looked at your code it works for most but, not in this case: [1, 3, 7, 10, 100] where we want 1 + 7 + 100. This is th reason why recursive function is used to get all combination from a list of numbers – Jul 27 '19 at 16:40

function stack overflow when 5000+ deep recursion

1 Answers1