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

Question

我有一个工作代码示例，用于为错误输入的单词查找可能的单词排列。例如，有人键入单词“gi”，因此建议的单词将是“go”或“hi”。给出了 find 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;
}

Answer 1

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

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

这一直持续到达到条件 index >= letters.Count() 为止。这次不会有递归调用，会返回一个包含一个空字符串的列表。在之前调用的函数中，此列表存储在参数 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