0

我有一个递归函数，它解析一个 trie 字符串数据库，替换为每个节点中的所有字符。在递归调用中，增加一个编辑计数，然后测试新字符串 1) 是否已解析所有节点，以及 2) 字符串是否等于已批准字符串列表中的字符串。因此，结果应该是测试字符串与数据库中所有可能的字符串之间的编辑距离。

void suggestCorrections(nodeT *w, Set<CorrectionT> &suggest, int index, string test, string final, double edits)
{   
    if (word == "") {
        if (containsCode(final)) //compare with list of approved strings
            updateSet(w, suggest, final, edits);

    } else  { //continue to search path
        if( w->alpha.size() > index) {
            if (test[0] == w->alpha[index].char)
                suggestCorrections(w->alpha[index].next, suggest, 0, test.substr(1), final+test[0], edits); //follow matching char 
            suggestCorrections(w, suggest, ++index, test, final, edits);//check next path
            suggestCorrections(w->alpha[index].next, suggest, 0, test.substr(1), final+w->alpha[index].char, ++edits);//follow path
        }
    }
}

struct CorrectionT {
    double editDistance; //stackItems
    string suggestedWord; //stackItems
    string suggestDescription;
    string gates;
};

问题是当 w->alpha.size() 等于 index 时 - 路径正确结束，但是suggestCorrections(w->alpha[index].next, suggest, 0, test.substr(1), final+w->alpha[index].char, ++edits);当 index 增加超过 w->alpha 的末尾时，输入了最后一个路径。为什么会这样？它是如何固定的？

我认为当路径结束时，它正在通过函数回溯。我不想让它倒退。我检查了调用堆栈和设置中断，但这似乎是一个概念问题而不是错误。我还阅读了关于递归的教科书章节和 Wikipedia 页面——我了解回溯的概念，但不了解这种特定情况下的实现（或所需的缺乏）。我使用回溯来构建 trie 数据库并且它在那里工作，但这与这里的不同之处足以让我无法弄清楚这一点。

4

1 回答 1

0

在对SuggestCorrections 的倒数第二次调用中，您传递了++index。那就是增加 index 的值，然后在最后一次调用SuggestCorrections 时将其传入。我并没有真正尝试理解您的代码，但看起来您可能只想在倒数第二个调用中传递 index+1，而不是 ++index。

通常，将增量操作隐藏在函数调用参数中并不是好的编码习惯（至少在我看来）。它使阅读和调试代码变得困难。

于 2012-08-02T23:56:28.440 回答