再帰の復習

再帰のコードを書こうと思ったがわからなくなったので、 Groovy で復習した。

コード

Group オブジェクトがあり、これらを Connection オブジェクトで連結する。

class Group {
    final String name
    Group(String name){
        this.name = name
    }
    String toString(){ return name }
}

class Connection {
    Group srcGroup
    Group dstGroup

    Connection(Group g0, Group g1){
        this.srcGroup = g0
        this.dstGroup = g1
    }

    String toString(){ return "@ connction: ${srcGroup} -> ${dstGroup}" }
}


def createConnection = { src,dst-> return new Connection(src, dst) }

def g0 = new Group('g0')
def g1 = new Group('g1')
def g2 = new Group('g2')
def g3 = new Group('g3')
def g4 = new Group('g4')
def g5 = new Group('g5')

def list = []

list << createConnection(g0, g1)
list << createConnection(g0, g2)
list << createConnection(g0, g3)
list << createConnection(g3, g4)
list << createConnection(g4, g5)

こうして作った connection オブジェクトのリストを使って、任意の group を指定すると、 その group 自体と子孫 group 全部をリストにして返す resolve という関数を持った MyResolver クラス:

class MyResolver {
    private final List list
    MyResolver(List list){
        this.list = list
    }

    List<Group> children(Group group){
        return list.findAll { it.srcGroup == group }.collect { it.dstGroup }
    }

    List<Group> resolve(Group group){
        def children = children(group)
        def hasChild = ( children.size>0 )
        if( !hasChild ){
            return [group]
        }
        else {
            return children.inject([group]){ a, b->
                a + resolve(b)
            }
        }
    }
}

resolve 関数が再帰になっている。

これを使うコード:

def myResolver = new MyResolver(list)
myResolver.resolve(g0).each { println '- ' + it }

g0 つまりルート相当の group オブジェクトを指定して実行すると:

- g0
- g1
- g2
- g3
- g4
- g5

もし、 g0 に代えて g3 を指定して実行すれば:

- g3
- g4
- g5

まとめ

Node.js での再帰 でも書いたコードを見ながら書いた。