How big is the stack to store recursive functions. What factors like OS, compiler, and hardware should I consider

Question

Hi I was running through a recursive code And I realized on my personal computer, running the default Visual Studio debugger I can only fit 6776 times when using the run without debugging option before I get a Stack Overflow Error. When using the debugger I was able to get it to 6781. On cpp.sh I was able to get too 900 million.I am suspecting caching but it still does not explain everything. Since it is more accurate than onlinegdb by a significant margin which only goes to 205000. My computer is significantly less capable than the server cpp.sh uses, but not 132,723 times less. What software and hardware trickery is being used and how to make it consistent?

I am running Windows 10 Version 1903 using an Intel N3350 with 4GB Ram.

int main()

{
    long double Answer = 0;
    Answer = 3 + (Solver(2, 1, UserInput, 0));
}
double Solver(int counter, int group, int stop, long double partialanswer)
{
    long double Counter = counter;
    if (Counter >= stop)
    {
        return partialanswer;
    }
    if (group % 2 != 0)
    {
        partialanswer = partialanswer + (4 / ((Counter) * (Counter + 1) * (Counter + 2)));
    }
    else
    {
        partialanswer = partialanswer - (4 / ((Counter) * (Counter + 1) * (Counter + 2)));
    }
    Solver((counter + 2), (group+1), stop, partialanswer);
}

Note 3 Here is the full code if you need it.

#include <iostream>
#include <iomanip>
#include <cmath>
using namespace std;
double Solver(int counter, int group, int stop, long double partialanswer)
{
    long double Counter = counter;
    if (Counter >= stop)
    {
        return partialanswer;
    }
    //partialanswer = round(partialanswer * pow(2, 54)) / pow(2, 54);
    if (group % 2 != 0)
    {
        partialanswer = partialanswer + (4 / ((Counter) * (Counter + 1) * (Counter + 2)));
    }
    else
    {
        partialanswer = partialanswer - (4 / ((Counter) * (Counter + 1) * (Counter + 2)));
    }
    Solver((counter + 2), (group+1), stop, partialanswer);
}

int main()

{
    int UserInput;
    long double Answer = 0;
    cin >> UserInput;
    Answer = 3 + (Solver(2, 1, UserInput, 0));
    cout << "PI = " << setprecision(18) << Answer << endl;
    cout << "reference Pi is equal to 3.1415926535897932384626433832795028841971 " << endl;
    cout << " The Difference is equal to " <<fixed << setprecision(30) << abs(Answer - 3.1415926535897932384626433832795028841971) << endl;
}

Subtraction Code

#include <iostream>
#include <iomanip>
using namespace std;


int main()
{
    long double UserInput1;
    long double UserInput2;
    cin >> UserInput1;
    cin >> UserInput2;
    cout << fixed << setprecision(32) << (UserInput1 - UserInput2);
}

cached 900,000,000 entry

cached 100,000,000 entry

subtraction code and run

[cached 100000000 before crash][6]

cached 900000000 after crash cached 100000000 after crash

cached Subtraction 60 digit code and run

----https://i.stack.imgur.com/j0QN2.png

stack and heap grow towards each other. the less objects you have, the larger is the space for stack's growth — mangusta, Oct 01 '19 at 22:23
Possible duplicate of [Does C++ limit recursion depth?](https://stackoverflow.com/questions/2630054/does-c-limit-recursion-depth) — Spencer, Oct 01 '19 at 22:25
Windows OSes are typically a 1MB stack. You can change this with the right build options, but they depend on your tool chain, which is blurry since you tag both GCC and Visual Studio. You are using Visual Studio with GCC? — user4581301, Oct 01 '19 at 22:26
MS-Linker option to set the stack size: https://learn.microsoft.com/en-us/cpp/build/reference/stack-stack-allocations?view=vs-2019 _"...Default stack size is 1 MB...."_ — Richard Critten, Oct 01 '19 at 22:26
@mangusta ; That may be true in a stand-alone system, but it is more complex than that in a modern desktop operating system environment. — Clifford, Oct 01 '19 at 22:27
And all bets are off with online compilers. Probably GCC, but who knows what the they are running and doing in the backend. — user4581301, Oct 01 '19 at 22:32
Note that the compiler may easily optimize your Solver function into loop and not to use stack for recursive calls. — Öö Tiib, Oct 01 '19 at 22:46
@Spencer I know that. He specified Windows which means x86 and x86 has both growing towards each other — mangusta, Oct 01 '19 at 22:53
mangusta know I am using both Visual Studio debugger, I am speculating cpp,sh is using gcc since some of the errors are linux specfic, though I could be wrong. I don't know I don't have a linux or a unix enviorment that I control. I am going to try to use my android phone. — S S, Oct 01 '19 at 22:54
Differences between systems may be down to differences in size of `long double`. — Clifford, Oct 01 '19 at 22:59
@mangusta In WIndows the heap is provided by the OS and virtualised. The amount of heap available to a process can change on demand. The stack is a fixed allocation determined when the code is linked. As I said it is more complex that you describe, but in any event it has no bearing on this question. — Clifford, Oct 01 '19 at 23:02
If your algorithms rely on heavy recursion, then Murphy's Law implies that you'll have more than sufficient stack space for your test data, but insufficient stack space when running in production. — Eljay, Oct 02 '19 at 03:08
Your code has undefined behavior: function `Solver` should return a value, but it does not when it recurses. So, all your tests with this particular code are moot. Anything can happen. — j6t, Oct 02 '19 at 05:30
@j6t Could you please elaborate or provide me other sources to find more information — S S, Oct 02 '19 at 20:08
@SS [Flowing off the end](http://www.eel.is/c++draft/stmt.return) of a function whose return type is not `void` is undefined behavior. Your function ends with just `Solver(...); }` instead of `return Solver(...); }`. That is UB. The compiler can do whatever it likes for those inputs that require that the function reaches that point. — j6t, Oct 03 '19 at 06:25

Clifford · Answer 1 · 2019-10-01T23:04:15.377

In Windows a typical thread stack size 1Mb (may differ between toolchains - GCC,VC++ etc., but that order of magnitude). To change the stack size consult your toolchain's documentation.

Each call will consume one stack frame, the size of which will be determined by the size of its local variables and parameters, plus the size of the return address and accounting for data alignment padding.

If your stack were 1Mb and you achieved a depth of 6776, that would suggest perhaps 154 bytes per call which seems somewhat high - I cannot account for that much from the code presented. A debug build may pad the stack frame to support overrun detection perhaps. Even so I would estimate perhaps 60 bytes, so still significant. A depth of 900 million might then require a stack of 50Gb which seems implausible.

In the debugger you could observe the SP register to see by how much it changes when you enter Solver(). However by running debugable code you are likely also to have disabled optimisations which may be the real answer to why you get greater performance on on-line systems.

n. m. could be an AI · Answer 2 · 2019-10-02T03:55:44.060

1

Why are results drastically different? One compiler optimises the recursion down to a loop. Another compiler, or the same one at another optimisation setting, does not. That's all there is to it.

How big the stack is? Each implementation usually documents it, and provides some means to change the value. The default for desktop operating systems is normally around 1 MiB.

edited Oct 02 '19 at 03:55

answered Oct 02 '19 at 03:49

n. m. could be an AI

112,515
14
128
243

I don't know whether I should delete this(question) but it was cached data. – S S Oct 02 '19 at 03:52
@SS I don't know what you mean by "cached data". – n. m. could be an AI Oct 02 '19 at 04:49
I have flagged the question for removal but pretty much entering 100 million is the same as 900 million, and cpp.sh is just not doing its job. Pretty much useless information – S S Oct 02 '19 at 05:08
@SS I have no idea what you mean by that last comment. Does the program output correct results? – n. m. could be an AI Oct 02 '19 at 05:18
No it's not doing it in a while loop will lead to a different results – S S Oct 02 '19 at 06:05
@SS sorry still not getting it. Are the results valid? Have you looked at the disassembly? – n. m. could be an AI Oct 02 '19 at 07:41
The compiler won't allow you – S S Oct 02 '19 at 15:45
It won't allow you what exactly? – n. m. could be an AI Oct 02 '19 at 16:13
You can't use the debugger, you can only run the compiled code – S S Oct 02 '19 at 19:55
The web interface maybe won't allow you to run the debugger. You don't have to use a web interface. There are many machines around with the exact same compiler and a more usable interface. – n. m. could be an AI Oct 02 '19 at 21:42
Could you give me the exact configuration of cpp.sh and I will try to replicate as much as possible – S S Oct 02 '19 at 22:39
@SS https://godbolt.org/z/kCpiqX look at the assembly. If you enable optimisations there are no recursive calls, only loops. – n. m. could be an AI Oct 03 '19 at 12:44
I'm sorry but I have not a slightest idea what you are talking about. Did you look at the disassembly? Have you found a recursive call there? – n. m. could be an AI Oct 04 '19 at 19:48
I just did, and I think ```.long 1073741824``` and ```.long 1082130432``` are the cause. – S S Oct 04 '19 at 20:53
I believe it has been shown that stack depth is irrelevant because your program is only using a small fixed amount of stack memory. If you have a different question (about precision or whatever) please ask a different question. – n. m. could be an AI Oct 04 '19 at 21:19

How big is the stack to store recursive functions. What factors like OS, compiler, and hardware should I consider

2 Answers2