C中的递归问题
Recursion problems in C
我正在使用 C 编写一个变位词求解器。遇到一个问题,求解器将 return 正确地处理前几个变位词,但是对于超过 2 个单词的变位词,它开始进入无限循环。
示例:
我在 anagram 求解器中输入 "team sale rest",它用 teamster ale 和其他一些响应。然后当它到达发布时,它进入一个无限循环,打印 "releases am matt" "releases am am matt" 等
这是代码库:
//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;
}
我是怎么读它的(我显然遗漏了一些东西)是它应该尝试匹配所有匹配项,如果不能匹配,它应该移动到找到的下一个字母子集。
我已经尝试使用调试器进行调试,但无法押韵或解释它的原因。
如上评论所述:
get_remaining_letters 使用原始结果->table[i][j] 并删除字母。这将为下一次迭代留下一个空字符串,并导致它无法按预期执行。通过将字符串复制到该函数内的临时字符串来修复。
我正在使用 C 编写一个变位词求解器。遇到一个问题,求解器将 return 正确地处理前几个变位词,但是对于超过 2 个单词的变位词,它开始进入无限循环。
示例:
我在 anagram 求解器中输入 "team sale rest",它用 teamster ale 和其他一些响应。然后当它到达发布时,它进入一个无限循环,打印 "releases am matt" "releases am am matt" 等
这是代码库:
//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;
}
我是怎么读它的(我显然遗漏了一些东西)是它应该尝试匹配所有匹配项,如果不能匹配,它应该移动到找到的下一个字母子集。
我已经尝试使用调试器进行调试,但无法押韵或解释它的原因。
如上评论所述:
get_remaining_letters 使用原始结果->table[i][j] 并删除字母。这将为下一次迭代留下一个空字符串,并导致它无法按预期执行。通过将字符串复制到该函数内的临时字符串来修复。