C ++ Проблемы рекурсии <confused>

Question

Я работаю над пониманием рекурсии, и я думаю, что у меня все в порядке ... Я пытаюсь создать функцию поиска (например, std :: string.find ()), которая ищет данную строку для другой строки например:

Дана (большая) строка: "бегущий кот"

строка поиска (маленькая): "run"

Я пытаюсь вернуть индекс для того, где слово, которое я ищу (в приведенном выше случае это будет ** 7), рекурсивный метод, который у меня есть, выглядит следующим образом - я не могу получить его верните индекс правильно.

вызов рекурсивной функции:

index = index_of(imput.c_str(), search.c_str())

Метод рекурсии:

int index_of( const char * i, const char * s) {
 int j;
 if (*s == '\0') { return; }
 if (*i == '\0') {
  return NULL;
 }
 else if ( *i == *s ) {
  index_of((i++), (s++));
 }
 else {
  j += index_of((i++), s);
 }
 return j;
}

Другая предвидимая проблема заключается в том, что когда (как в примере - ОК, это отстой, но мне нужен тот, который работал), он достигает "ru_", он все еще застрял на " сбросить указатель s?

Answer 1

1. Не изменяйте никакие переменные состояния. Ваш код не должен содержать оператор ++ в любом месте . Вы не пытаетесь перебрать структуру данных и каким-то образом изменить свои локальные переменные - вы пытаетесь каждый раз создавать совершенно новую, но меньшую проблему. Итак, все эти ++ операторы - будь то до или после приращения - являются красными флагами.

2. У вас более одной подзадачи. (... поэтому рекурсия одной функции не идеальна).

   Давайте посмотрим на это систематически.

   Предположим, у вас есть рабочий index_of, и вы просто хотите вызвать его с входом, который короче вашего, и что стог сена и игла еще не пусты. Тогда одна из двух вещей может быть:

   • Стог сена начинается с той же буквы, что и игла, и вам просто нужно взглянуть немного глубже, чтобы убедиться в этом.
     - Что произойдет, если проверка прошла успешно - что если она не пройдет? это подзадача index_of?

   • ... или стог сена начинается неправильно, и вам нужно смотреть глубже.
     - Глубоко ли заглядывает в стог сена подзадача index_of?

   Обратите внимание, что если стог сена запускается OK, это не обязательно означает, что он начинается с full строки поиска - и если он запускается OK, но не начните с полной строки поиска, вам действительно не нужно продолжать поиск. Это означает, что подзадача «начинается с» принципиально отличается от подзадачи «индекс»:

   • index_of : здесь, неспособность найти строку поиска по индексу 0 означает, что вам нужно искать дальше.
   • start_with : здесь, неспособность найти строку поиска по индексу 0 означает, что вам нужно остановиться.

   Можно можно сказать startswith(haystack, needle):= 0==index_of(haystack, needle), но, очевидно, index_of - более сложная проблема с более дорогим решением - так что вы не должны этого делать; поначалу это еще более запутанно.

3. Определите ваши базовые случаи - Что означает пустая игла или стог сена?

4. Добрые имена помогают прояснить ситуацию, а рекурсию трудно читать в лучшие времена - например, в ответе Якоби есть несколько значимых вариантов выбора.

Резюме

Я не собираюсь решать вашу собственную головоломку для вас, но несколько советов в резюме ...

• Избегайте изменения локальных переменных: вы пытаетесь определить подзадачу, а затем просто вызвать правильную функцию для этих более новых, более коротких параметров. Не используйте побочные эффекты, они делают вещи ужасно сложными.
• Рекурсия не обязательно означает только одну функцию A, вызывающую A - это может быть любой циклический граф вызовов, который в конечном итоге завершается; Вы можете использовать больше функций
• Если игла и стог сена начинаются с одной и той же буквы, это не означает, что вся игла находится в начале стога сена, а если это не так, вам все равно нужно продолжить поиск
• Эта строка неверна: if (*s == '\0') { return 1; }

Answer 2

Это то, как я бы это сделал, что упрощает все, перемещая его в разные функции. Не проверено, но, надеюсь, это даст вам представление.

/**
 * Checks if one string starts with another string. This returns an
 * incorrect result if it is called where prefix is an empty string.
 */
bool starts_with_impl(const char* haystack, const char* prefix) {
    if ( *prefix == 0 ){ 
        //reached the end of prefix without having found a difference in characters
        return true;
    }else if ( *haystack == 0 || *prefix != *haystack ){
        //either prefix is longer than haystack or there is a difference in characters.
        return false;
    }
    //move along the haystack and prefix by one character
    return starts_with_impl(++haystack, ++prefix);
}
/**
 * Wrapper around starts_with_impl that returns false if prefix is an empty string
 */
bool starts_with(const char* haystack, const char* prefix) {
    return *prefix ? starts_with_impl(haystack, prefix) : false;
}

int get_substr_impl(const char* haystack, const char* const needle, int index) {
    if ( *haystack == 0 ){
        //reached the end of haystack with no match, -1 is no string found
        return -1;
    }else if ( starts_with(haystack, needle) ){
        //we have found a substring match.
        return index;
    }
    //move along haystack by one character
    return get_substr_impl(++haystack, needle, ++index);
}
/**
 * Wrapper function for the above to hide the fact we need an additional argument.
 * I am avoiding using a default argument as it makes a messy api
 */
int get_substr(const char* haystack, const char* const needle) {
    return get_substr_impl(haystack, needle, 0);
}

Из комментариев

у вас есть 2 константы в методе get_substr_impl ....

Преднамеренное.

// means that the data is constant, in other words I can't change the value of needle
const char* needle;

//means that as well as the data being constant 
//I can't change the address that the pointer points to.
const char* const needle;

из основного метода я бы не вызвал get_substr_impl с теми же параметрами, что и в get_substr?

Я разделил его, так как get_substr_impl имеет дополнительный (обязательный) аргумент int index, который необходим для внутренней работы функции и всегда должен начинаться с 0. Хотя вы можете вызвать get_substr_impl("abc", "a", 0);, он выглядит лучше более понятно звонить get_substr("abc", "a"); и избегать ошибок (например, звонить get_substr_impl("abc", "a", 1);)

Answer 3

Прежде всего, у вас есть два i в вашем коде. Это не должно даже компилироваться.

Кроме того, index_of((i++), (s++)); фактически совпадает с:

index_of(i, s); 
++i;
++s;

Другими словами, вы вызываете index_of over & over с теми же параметрами, которые были вызваны в первый раз. (он никогда не вернется, чтобы добраться до ++ i).

Кроме того, чисто стилистический, но так как тип возвращаемого значения - int, вы должны вернуть 0 и сохранить NULL для использования с указателями.

Answer 4

Основная проблема здесь в том, что вы используете постинкремент, и результатом (i ++) является i. Вы должны использовать ++ I