c# - 需要了解递归在查找单词排列代码示例中如何工作

Question

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

我需要了解 sub_words 如何获取值。由于该函数是递归调用的，因此 char[] approximation_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;
}

Answer 1

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

看一下参数index，每次都会累加。一开始，rightget_nearby_permutations() 将被调用 index = 0。在函数内部，您有一个带有 ++index 的递归函数调用，这意味着索引将加一。

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

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

专业提示:使用调试和断点来检查代码正在做什么。

编辑:递归调用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