Stack Overflow Error With This Recursive Program? - C++

Question

I'm a programming student in my first C++ class, and recently we were given an assignment to implement a recursive program that finds the first occurrence of a given substring in a given string.

For example:

int StringIndex("Mississippi", "sip"); // this would return 6

The hint we are given is to use a recursive helper function that takes the index as a parameter.

Here is what I've done so far:

int index_of(string s, string t)
{
    int index = 0;

    if (s[index] == NULL)
        return -1;
    else if (starts_with(s, t, ++index))
    {
        return index;
    }
    return index_of(s, t);
}

bool starts_with(string s, string t, int index)
{
    if (t[index] != s[index] || s[index] == NULL)
        return false;
    return starts_with(s, t, ++index);
}

I am getting a stack overflow error, and I don't understand why. So would somebody mind helping me understand why I'm getting this error? And help me get pointed in the right direction as to how to fix it?

Try stepping through the running of the routine with a debugger, or if you don't want to mess with a debugger, put printf() calls at various points in the functions. Then run your program with the output redirected to a file, and after it crashes, examine the file's contents... from the contents of a file, you'll be able to see what your program was doing and it will become clear why it recursed indefinitely and overflowed the stack. — Jeremy Friesner
– Jeremy Friesner, Commented Feb 21, 2010 at 20:20

R Samuel Klatchko · Accepted Answer · 2010-02-21 19:34:23Z

6

int index_of(string s, string t)
{
    ...

    // Your are calling yourself without modifying the
    // input parameters.  If you get here once, you'll
    // never break out.
    return index_of(s, t);
}

Nothing changes s or t so this can never stop.

answered Feb 21, 2010 at 19:34

R Samuel Klatchko

77k17 gold badges139 silver badges189 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

falstro Over a year ago

also, ++index makes little sense. In fact, the entire variable within index_of makes little sense..

stmax · Accepted Answer · 2010-02-21 19:48:01Z

When writing recursive functions you should always keep two things in mind: you need stop conditions which end the recursion and you have to get closer to a stop condition with each function call. If you fail to check stop conditions or if your function doesn't get closer to a stop condition during each call, you'll run into stack overflows (or infinite loops).

The problem in your first function is that it doesn't get closer to the stop condition. At the end you "return index_of(s, t)" without modifying s or t in the meantime. So the function will start over with the same parameters, again and again until you run into a stack overflow.

Another problem is in your starts_with function. It only returns false but never true.

score 2 · Accepted Answer · 2010-02-21 19:40:46Z

2

When you say:

s[index] == NULL

you should be aware that C++ std::strings need not be null-terminated internally - use the string's size() member function instead instead. Also, you are passing the strings by value, which for long strings could rapidly eat up stack space and dynamic memory . Pass them as const references instead:

bool starts_with( const string & s, const & string t, int index)
{
   ...
}

And lastly, as others have pointed out, only ONE of the functions, in this case starts_with() should be recursive. In fact, index_of() seems rather pointless.

edited Feb 21, 2010 at 19:40

answered Feb 21, 2010 at 19:32

anon

1 Comment

Thomas Over a year ago

Additionally, the order in the condition t[index] != s[index] || s[index] == NULL should be reversed, otherwise you'll be checking beyond the boundary before checking the boundary itself.

Goz · Accepted Answer · 2010-02-21 19:55:28Z

1

A) "starts_with" NEVER returns a true. So you never exit the index_of recursion.
B) index_of doesn't do anything on the recurse it just calls itself again with the same information.

Basically the 2 above problem leads to an infinite loop. You constantly check the same information and don't have the possibility of exiting that loop.

answered Feb 21, 2010 at 19:55

Goz

62.5k26 gold badges131 silver badges212 bronze badges

Comments

Community · Accepted Answer · 2017-05-23 11:50:53Z

1

If you'll pardon a way of pointing out the error that some might consider just a little too cute, consider the difference between:

See this answer

and:

If you don't understand see this answer

edited May 23, 2017 at 11:50

CommunityBot

11 silver badge

answered Feb 21, 2010 at 20:38

Jerry Coffin

494k83 gold badges656 silver badges1.2k bronze badges

3 Comments

Dan Over a year ago

Off topic but I'm curious: How did you know what the link would be before submitting your answer? It doesn't look like you edited to patch it up.

Jerry Coffin Over a year ago

@Dan:actually I did edit it. As far as I can tell, if you edit within a few seconds, it doesn't show it as an edit.

DSimon Over a year ago

Voted up for being both a valid (if somewhat confusing) answer, and a koan.

Collectives™ on Stack Overflow

Stack Overflow Error With This Recursive Program? - C++

5 Answers 5

1 Comment

Comments

1 Comment

Comments

3 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

5 Answers 5

1 Comment

Comments

1 Comment

Comments

3 Comments

Your Answer

Sign up or log in

Post as a guest

Related