需要了解递归是如何在查找单词排列代码样本中工作的

本文关键字：代码 排列 单词 样本 工作 查找 了解 递归 | 更新日期: 2023-09-27 17:55:17

我有一个工作代码示例，用于查找错误键入单词的可能单词排列。例如，有人键入单词"gi"，因此建议的单词为"go"或"hi"。给出了求get_nearby_letters()和isWord()的函数。

我需要了解sub_words是如何获得值的。既然函数是递归调用的，那么char[] nearby_letters = get_nearby_letters(letters[index-1]);程序语句是如何到达的呢？

我似乎很难理解递归函数是如何工作的。

public List<string> nearby_words(string word)
{
    List<string> possible_words;
    char[] letters = word.ToCharArray();
    possible_words = get_nearby_permutations(letters, 0);
    possible_words = possible_words.Where(x => isWord(x)).ToList();
    return possible_words;
}
public List<string> get_nearby_permutations(char[] letters, int index)
{
    List<string> permutations = new List<string>();
    if (index >= letters.Count())
    {
        permutations = new List<string> { "" };
        return permutations;
    }
    List<string> sub_words = get_nearby_permutations(letters, ++index);
    char[] nearby_letters = get_nearby_letters(letters[index-1]);
    foreach (var sub_word in sub_words)
    {
        foreach (var letter in nearby_letters)
        {
            permutations.Add(letter+sub_word);
        }
    }
    return permutations;
}

需要了解递归是如何在查找单词排列代码样本中工作的

函数rightget_nearby_permutations()是递归的，因为它在函数内部调用自己。现在您想知道递归调用之后的部分是如何到达的。

看一下参数index，它每次都会向上计数。在开始时，rightget_nearby_permutations()将被称为index = 0。在函数内部，您有一个使用++index的递归函数调用，这意味着索引将被加1。

这种情况一直持续到达到条件index >= letters.Count()。这一次将不会有递归调用，并且将返回一个包含一个空字符串的List。在之前调用的函数中，此列表存储在参数sub_words中。

现在一切都在倒退，递归调用后的行将被到达并填充排列。

ProTip：使用调试和断点来检查代码正在执行的操作。

编辑：letters.Count()==2:递归调用示例

Function 1
index = 0
Recursive call of    Function 2
                     index = 1
                     Recursive call of    Function 3
                                          index = 2
                                          index >= letters.Count() == true
                                          return
                     continue with f2
                     return permutations
continue with f1
return permutations

sub_words是如何获取值的

局部变量CCD_ 14接收对CCD_ 15方法的方法调用的返回值。

如何达到char[] nearby_letters = get_nearby_letters(letters[index-1]);程序语句？

该程序语句在上一次对get_nearby_permutations()的调用返回后执行。它的工作原理与方法调用之后的任何程序语句一样。

Stack Overflow并不是了解递归的最佳方法。这是一个广泛的话题，通常需要与学生握手，让他们了解细节。你应该阅读维基百科上的文章Recursion(计算机科学(和《在通俗英语中，什么是递归》？Q&programmers.stackexchange.com.

它的核心，递归是两件事：

  • 调用自身的方法(函数(，以及
  • 一个或多个终止情况，即方法不调用自身的原因

在您的示例中，该方法调用自身以获得对当前索引之后的输入的操作结果。IMHO，应该这样写：

List<string> sub_words = get_nearby_permutations(letters, index + 1);
char[] nearby_letters = get_nearby_letters(letters[index]);

这将更清楚地表明，您并不是真的希望在方法的当前调用帧中为index添加一个新值，而是下一次的调用应该使用递增的值。当变量稍后在当前调用帧中使用时，先增加值，然后再减去它，这既令人困惑又效率低下。

很明显，你有第一部分。第二部分是不调用自己的原因，因为每次调用自己时，index值都会增加一。最终，index值足够大，没有更多的字符需要处理，并且返回包含空字符串的列表，而不是方法调用自己。

这就是递归方法的基本工作方式。当然，还有更多的东西。毕竟，这种方法也确实有效。但这只是普通的算法。也就是说，给定递归调用的结果，现在该方法将创建当前字母与递归调用返回的各种字符串的不同组合。

由于该方法第一次返回，它只是返回一个带有空字符串的列表，所有的"组合"都只是当前字母附近的字母。但是，这些字母会作为sub_words值返回给该方法的上一次调用，此时它会将这些值与前一个字母的附近字母组合起来。

通过这种方式，该方法又回到了过去，通过尝试所有不同的字母组合和之前确定的每个较短的字母组合来创建可能单词的不同排列。

考虑到所有这些，您的下一步应该只是使用调试器将逐步进入方法。您会发现，每次调用该方法时，index值都会增加一，直到该方法最终从termination子句(即包含空字符串的列表(返回，然后，每次返回列表时，都会根据当前字母和上一个列表生成更长的列表。

调试器在理解这些代码方面可以提供非常丰富的信息。我建议你把它作为下一步尝试的事情之一。：(

相关文章：