How to avoid stack overflow when using recursion ?

general
, , ,
1

[Problem Statement][1] from Topcoder, Limits: Memory 64 MB

Here is the


[2] . It gives segmentation fault if input is greater than 131000 in ideone. i.e 131000 function stack frames

How to estimate if a recursion solution will use too much stuck memory resulting in a segmentation fault ?

What is the memory usage of one function stack frame ?


  [1]: http://community.topcoder.com/stat?c=problem_statement&pm=11361&rd=15697
  [2]: http://ideone.com/TKoSvY
2

I am going to make a few assumptions first:

  1. The amount of memory available to you during the competition is 512 MB.

  2. Your recursive code has simple data types as parameters and returns a simple value. (Objects --> Complex)

You can make around 9000 function calls in these conditions. Figure out your code complexity, and check if it asks for more than these number of recursive steps.

The way to find the maximum sustainable value is very interesting. After writing down the code on ideone, set n=10000. Now use binary search to find the maximum value of n where you have a segmentation fault.

Try this yourself and see if your code times out for large input. And btw, please tell me the max value for which your code works. :slight_smile:

3

It gives segmentation fault if input is greater than 131000 in ideone

4

It depends on the stack size.

Your function uses 8 bytes per function call because it has 2 integer (4 bytes) parameters and no local variables.
So, the number of recursive function call is stack_size / 8. It seems that ideone only provides 1mb stack size because 1024*1024 / 8 = 131072.

1 Like
5

I think @mogers has the right approach, but the computation is not quite right.

You have local variables in your (machine) code. Although not visible at the C+±Level, the machine code will need locals to store the intermediate results (the values of f which are used as parameters in successive function calls.

For each function call you will have to store administrative stuff like the return value, return address and other stuff. It obviously depends on the compiler and the machine architecture. My guess would be that ideone uses at least 4, propably 8 (the standard linux value ) of max stack memory.

For making an estimate it depends on the max amount of stack allowed. For codechef and sphere it’s relatively small. So trouble will start at about 10^5 recursive calls (as in your case). Some sites use large values of stack size (>100MB). In this case you can go up to 10^6. If you need more function calls your algorithm is probably not the right one anyway.

6

things like return value and intermediate results are usually in CPU registers, not the stack.

7

I faced this problem only on topcoder. Here is a link which is of further help.

Codeforces system stack is so huge 256 MB, unlike TopCoder which has only 8 MB