Что не так с этим рекурсивным кодом?

Question

Что не так с этим рекурсивным кодом?

Я делаю работу в Интернете с использованием CodeLab для C ++ и не уверен, что не так с моим кодом. Вот вопрос:

Напишите рекурсивную int-значимую функцию len, которая принимает строку и возвращает количество символов в строке.
Длина строки:
0, если строка является пустой строкой («»).
На 1 больше длины остальной части строки после первого символа.

И вот мой код:

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

Это говорит, что у меня есть ошибка во время выполнения.
Любая помощь?

Благодарю.

1

c++recursion stack-overflow

Решение

Другие решения

Вы никогда не модифицируете s в вашем коде, так что если s не пусто, вы продолжаете вызывать ту же функцию и снова, с тем же параметром; Вы никогда не останавливаетесь. На вашем компьютере не хватает места в стеке, и программа падает.

Другие дали вам некоторые идеи / варианты. Вот мое предложение:

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

Если предположить, str длина строки, которую вы хотите получить, вы можете назвать ее так: len(str, 0)

Если вам нужно использовать const char * Версия попробуйте это:

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) никогда не уменьшится и не вызовет переполнение стека. Я хотел бы сделать что-то вроде:

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

3

Другое решение:

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

0

Источник

Accepted Answer

Ну вот:

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

Длина строки никогда не уменьшается. Таким образом, вы в конечном итоге получите переполнение стека, потому что вы никогда не достигнете базового варианта (s.length() == 0). Вам нужно получить подстроку, где длина s уменьшается на 1:

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

Надеюсь, это чисто академический, потому что std::string имеет length метод, который будет работать в постоянном времени. (Не говоря уже о том, что стирание с начала строки, возможно, ужасно неэффективно — посмотрите другие ответы, которые работают с char *)

11