java如何避免在递归中重复

Question

我试图以递归方式搜索同义词(我称之为'synset').不幸的是,有同义词的重复.例如:当我搜索单词student时,输出将如下所示:

Search word: student

Synset 0: pupil
  Synset 0: student
    Synset 0: pupil
    .
    .
    .
  Synset 1: educatee
  Synset 2: schoolchild
Synset 1: educatee
Synset 2: scholar
Synset 3: bookman

我想将所有输出存储到数据库中,我不需要重复输出.这是我的代码的一部分,包括递归函数.希望有人能帮助我......谢谢

public String printSynset(String word)
    {
        //call wordnet library

        RiWordnet wordnet = new RiWordnet();
        //call stemmer method
        PorterStemmer s = new PorterStemmer();


    Vector<String> synsetVec = new Vector<String>();
    String[] synset = wordnet.getAllSynsets(word, "n");

    for (int k=0; k<synset.length; k++)
    {
        synsetVec.add(synset[k]);

        if (!synsetVec.isEmpty())
        {
            for (int j = 0; j < synsetVec.size();) 
            {   
                GUIsynonymTA.append("\n");
                GUIsynonymTA.append("   No." + j + ": " + (s.Stem(synsetVec.get(j))));
                GUIsynonymTA.append("\n");

                return printSynset(synsetVec.get(j));
            }
        }

        else if (synsetVec.isEmpty())
            return word;

    }
    return word;
}//end printSynset()

Answer 1

你应该保留Set一些你已经看过的物品.每当你点击一个项目时,首先要检查它是否曾被看过; 如果是,停止递归; 如果不是,请将其添加到集合中并继续.

结果是一般图形的经典深度优先搜索,您可以在任何算法教科书或Russell&Norvig第3章中找到它.伪代码:

Set<Node> printSynset(Node root) {
    HashSet<Node> closed;
    printDFS(root, closed);
}

// recursive graph dfs
void printDFS(Node n, Set<Node> closed) {
    if (!closed.contains(n)) {
        print(n.item);
        closed.add(n);
        for (Node s : n.neighbors())
            printDFS(n, closed);
    }
}

请注意,当printDFS返回时printSynset,它将填充closed它访问过的所有节点,因此您也可以选择返回它Set<Node>并在其上循环printSynset,而不是执行打印printDFS.这将为您提供一个通用的,可重复使用的DFS例程.