1

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.

1
  • 2
    I doubt that the assignment wants you to use an std::string. It looks more like it wants you to manually determine the length of a const char* string.
    – Nikos C.
    Dec 7, 2012 at 21:57

4 Answers 4

11

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 *)

3
  • 5
    Damn it... my boss swung by and I had to stop typing... +1 :D Dec 7, 2012 at 21:56
  • I see what you are saying, but it says "1 more than the length of the rest of the string beyond the first character", how do I interpret this?
    – Alti
    Dec 7, 2012 at 22:00
  • A stackoverflow. How apropo! Dec 8, 2012 at 1:58
3

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);
}
3

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); 
}
0

Another solution:

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.