scala - Scala：递归搜索避免循环

Question

如何编写避免循环的递归搜索。

我的课是这样的：

class Component(var name: String, var number: Int, var subComponent: Set[Component])

现在我需要一种方法来检查一个组件是否包含在其子组件内或在其子组件的子组件之间等等。避免由其他组件引起的可能循环。

我的递归搜索方法必须具有以下签名，其中 subC 是 comp 的 Set [component]。

def content (comp: Component, subC: Set[Component]) : Boolean = {
}

谢谢您的帮助。

Answer 1

visited一种方法是使用累加器定义内部函数。

def content (comp: Component, subC: Set[Component]) : Boolean = {
    def contained(comp: Component, subC: Set[Component], visited: Set[Component]): Boolean = {
        // over time (recursion) add components to visited
        // you can then use 
        //    visited contains comp
        // to check existence and 
        //    visited diff subC
        // to get the unvisited components

    }
}

Answer 2

实现这一点的最简单方法是保留一组已访问的组件。这可以定义为方法中的方法。该方法将执行递归。它将访问集作为一个额外的参数，并以一个空集启动。