Проблемы рекурсии в C - PullRequest
Новая
       27

Проблемы рекурсии в C

0 голосов
/ 15 февраля 2020

Я работаю над решателем анаграмм в C. Задайте проблему, когда решатель вернет первые несколько анаграмм правильно, однако для тех, которые выходят за два слова, он начинает вводить бесконечный l oop.

Пример:

Я ввожу "отдых команды продажи" в решатель анаграмм, он отвечает с элем Teamster и несколько других. Затем, когда он достигает выпусков, он входит в бесконечное число l oop, где печатает «release am matt», «release am am matt» et c.

Вот база кода: 

//recursively find matches for each sub-word
int findMatches(char string[], char found_so_far[])
{
    printf("String entering function: %s\n", string);
    int string_length = strlen(string);
    int_char_ptr *results = getPowerSet(string, string_length);
    if(!results)
        return 2;
    // selects length of subset, starting with the largest
    for (int i = string_length - 1; i > 0; i--)
    {
        // iterates through all the subsets of a particular length
        for(int j = 0; j < results->count[i]; j++)
        {
            word_array *matches = NULL;
            // check words against dictionary
            matches = dictionary_check(results->table[i][j]);
            if (matches)
            {
                // iterate through matches
                for(size_t k = 0; k < matches->size; k++)
                {
                    int found_length;
                    // find out length of string needed for found
                    if (strcmp(found_so_far, "") == 0)
                        found_length = strlen(matches->arr[k]) + 1;
                    else
                        found_length = strlen(found_so_far) + strlen(matches->arr[k]) + 2;
                    char found[found_length];

                    // on first passthrough, copy directly from matches
                    if (strcmp(found_so_far, "") == 0)
                        strcpy(found, matches->arr[k]);
                    else
                        sprintf(found, "%s %s", found_so_far, matches->arr[k]);
                    char tempstr[string_length];
                    strcpy(tempstr, string);
                    char *remain = get_remaining_letters(tempstr, results->table[i][j]);
                    // if there are no letters remaining
                    if (strcmp(remain, "") == 0)
                    {
                        printf("MATCH FOUND: %s \n", found);
                        // alternatively, could store strings to array
                    }
                    else
                    {
                        findMatches(remain, found);
                    }
                }
            }
        }
        free(results->table[i][results->count[i] - 1]);
        free(results->table[i]);
    }
    return 0;
}

Как я читаю это (я явно что-то упускаю), это то, что он должен пытаться сопоставить все совпадения, а если нет, он следует перейти к следующему подмножеству найденных букв.

У меня есть попытки пройти с отладчиком, и я не могу сделать рифму или причину этого.

1 Ответ

0 голосов
/ 15 февраля 2020

Как указано выше в комментарии:

get_remaining_letters использовал исходные результаты-> table [i] [j] и удалил буквы. Это оставит пустую строку для следующей итерации и заставит ее работать не так, как ожидалось. Исправлено копированием строки во временную строку внутри этой функции.

...