C++ Stack Overflow with 20,000 size string

Question

My simple program source code is following and it find the (nested) parenthesis pair and repeat the string.

2(R) -> RR

#include <iostream>
#include <string>
#include <stack>
using namespace std;

string repeated(string str, int n){
    string repeat;
    for(int _=0; _<n; _++)
        repeat.append(str);
    return repeat;
}

string solution(string rgb, int recurdepth) {
    stack<int> s;

    for(int i=0; i<rgb.size(); i++){
        if(rgb[i]=='(') {
            s.emplace(i);
        }
        else if(rgb[i]==')') {
            int startp = s.top();
            char command = rgb[startp-1];
            string childstr = rgb.substr(startp+1, i-(startp+1));
                
            string tmp2;
            tmp2 = repeated(childstr, (int) command - '0');

            rgb.erase(startp-1, i+1-(startp-1));
            rgb.insert(startp-1, tmp2);
            
// change the string and start from first
            return solution(rgb, recurdepth+1);
        }
    }
// if there are no parenthesis, just return
    return rgb;
}

int main(int, char**) {    
    string in1;
    for(int i=0; i<5000; i++) in1.append("2(R)");
    cout<< in1.size() << endl;
    string answer = solution(in1, 1);
    cout << answer.size() << endl;
    cout << "answer: " << answer << endl;
}

I encountered this Stack Overflow error with MSVC, but not occured in WSL2 ubuntu 20.04 clang-10. I tested in Visual Studio 2019.

Unhandled exception at 0x00007FFFF99FE798 (ntdll.dll) in ConsoleApplication1.exe: 0xC00000FD: Stack overflow (parameters: 0x0000000000000001, 0x000000B0F6003FD8).

What's wrong with this? I debug this with VS, but i don't know what's wrong.

Recursion can do that to you. You may have to find a non-recursive solution or be a lot sneakier with how you're allocating storage. — user4581301, Nov 01 '20 at 03:30
Linux by default have an 8 MiB stack per process, while Windows only have a single 1 MiB stack. That would probably explain the different in behavior. — Some programmer dude, Nov 01 '20 at 03:33
As I know that though string variable declared in stack, it allocated in heap. Is this error associated with it? — varvir, Nov 01 '20 at 03:40
The recursion depth is limited. The string will have 24 or so bytes per recursion — drescherjm, Nov 01 '20 at 03:41
Recursion. Function calls on almost all systems uses the stack for the data bout the call as well as the local variables. Deep recursion will exhaust the stack. — Some programmer dude, Nov 01 '20 at 03:43
That's very useful information about your problem. Please add that to the question, as well as any other information you have. Without that information, there's not really much we can do other than point you to [this](https://stackoverflow.com/questions/15976333/stack-overflow-caused-by-recursive-function). — cigien, Nov 01 '20 at 03:45
*"though string variable declared in stack, it allocated in heap"* -- misleading use of "it". The *character data* is allocated on the heap, at least once the string is over a dozen or so characters. However, the *variable* -- which (likely) consists of a pointer to the character data, a size, and a capacity -- is allocated where the variable is declared (on the stack). Space is required on the stack for each of your string variables. — JaMiT, Nov 01 '20 at 03:49
I tested this code on VS 2019 and it does crash with a stack overflow in debug or release mode. I did not verify the recursion depth however. — drescherjm, Nov 01 '20 at 03:49
I saw a recursion depth of 3045 before it crashed in release mode. — drescherjm, Nov 01 '20 at 03:56
I'm glad you solved your problem :) However, you shouldn't add the answer where the question is supposed to be. Instead, as Joshua mentioned, you can post that as an answer. — cigien, Nov 01 '20 at 04:28

score 2 · Answer 1 · edited Nov 01 '20 at 04:49

I solved my problem by changing my recursion code to iteration code.

#include <iostream>
#include <string>
#include <stack>
using namespace std;


string repeated(string str, int n) {
    string repeat;
    for (int _ = 0; _ < n; _++)
        repeat.append(str);
    return repeat;
}

string solution(string rgb) {
    bool isthereparen = true;
    stack<int> s;

    while (isthereparen)
    {
        for (int i = 0; i < rgb.size(); i++) {
            if (rgb[i] == '(') {
                s.emplace(i);
            }
            else if (rgb[i] == ')') {
                isthereparen = false;

                int startp = s.top();
                char command = rgb[startp - 1];
                string childstr = rgb.substr(startp + 1, i - (startp + 1));

                string tmp2;
                tmp2 = repeated(childstr, (int)command - '0');

                rgb.erase(startp - 1, i + 1 - (startp - 1));
                rgb.insert(startp - 1, tmp2);
                break;
            }
        }

        if (isthereparen == false) {
            isthereparen = true;
        }
        else {
            isthereparen = false;
        }
    }

    return rgb;
}

int main(int, char**) {
    string in1;
    for (int i = 0; i < 10000; i++) in1.append("2(R)");
    cout << in1.size() << endl;
    string answer = solution(in1);
    cout << answer.size() << endl;
    cout << "answer: " << answer << endl;
}

Yeah, I know this is not the best iteration code, and I prefer recursion to iteration, but this works.

C++ Stack Overflow with 20,000 size string

1 Answers1