具有修剪搜索的递归回溯

Question

我有一个递归函数，该函数解析一个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时-路径正确结束，但是当index增加到w-> alpha的末尾时，最后一条路径suggestCorrections(w->alpha[index].next, suggest, 0, test.substr(1), final+w->alpha[index].char, ++edits);被输入。为什么会这样呢？以及如何解决？

我认为在遇到路径的末尾时，它将通过该函数回溯。我不希望它回溯。我检查了调用堆栈并贯穿了整个安装过程，但这似乎是一个概念性问题，而不是错误。我还阅读了有关递归和Wikipedia页面的教科书章节-我了解回溯的概念，但不了解特定情况下的实现（或期望的实现）。我使用回溯建立了特里数据库，并且在那里工作了，但是与这里的差异足够大，我无法弄清楚。]

我有一个递归函数，该函数解析一个trie字符串数据库，替换为每个节点中的所有字符。在递归调用上，将增加一个编辑计数，然后测试新字符串的...

Answer 1

倒数第二个对suggestCorrections的调用中，您正在传递++ index。那就是增加index的值，然后在最后一次对suggestCorrections的调用中传递该值。我还没有真正尝试理解您的代码，但是您似乎只想在倒数第二个调用中传递index + 1，而不是++ index。