CODEWITHSUNDEEP
c++recursionstack-overflow
Alti
Alti

Reputation: 189

What is wrong with this recursive code?

I am doing online work using CodeLab for C++ and am not sure what's wrong with my code. Here is the question:

Write a recursive, int-valued function, len, that accepts a string and returns the number of characters in the string. The length of a string is: 0 if the string is the empty string (""). 1 more than the length of the rest of the string beyond the first character.

And here's my code:

int len(string s)
{
  if (s.length()==0)
    return 0;
 else
 {
    return 1+(len(s)-1);
 }
}

It says I have a run-time error. Any help?

Thanks.

Upvotes: 1

Views: 2272

Answers (4)

Faruk Sahin
Faruk Sahin

Reputation: 8756

len(s) will never decrease and cause a stackoverflow. I would do something like:

int len(const char * s) {
    if(*s == '\0')
        return 0;
    else
        return 1 + len(s+1); 
}

Upvotes: 3

Doug T.
Doug T.

Reputation: 65649

Well here:

     return 1+(len(s)-1);

The length of the string never decreases. So you will eventually have a stackoverflow because you never hit your base case (s.length() == 0). You need to get a substring where the length of s decreases by 1:

     return 1+(len(s.erase(0,1))); // erases 1 char from beginning then recurses

Hopefully this is purely academic, because std::string has a length method that will run in constant time. (Not to mention erasing from the front of a string is probably horribly inefficient-- see the other answers that work with char *)

Upvotes: 11

Houari
Houari

Reputation: 5651

Another solution:

int len(string s)
  {
  if (s.length()==0)
      return 0;
  else
     {
     s = s.substr(0, s.size()-1);
     return 1+(len(s));
     }
  }

Upvotes: 0

Nik Bougalis
Nik Bougalis

Reputation: 10613

You are never modifying s in your code, so if s is not empty you keep calling the same function and again, with the same parameter; your never stop. Your computer runs out of stack space and the program crashes.

Others have given you some ideas/options. Here's mine suggestion:

int len(const std::string &s, int start)
{
    /* If we are starting at the end, there's no more length */
    if(start == s.length())
        return 0;

    /* one plus whatever else... */
    return 1 + len(s, start + 1);
}

Assuming str is the string you want to get the length of, you can call it as: len(str, 0)

If you need to use a const char * version try this:

int len(const char *s)
{
    if((s == NULL) || (*s == 0))
        return 0; /* we ran out of string! */

    return 1 + len(s + 1);
}

Upvotes: 3

Related Questions