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 例程。