Loading...

Thursday, April 28, 2011

Groovy Goodness: Recursion with Closure Trampoline Capability

When we write recursive code we might get a stack overflow exception, because calls are placed on the stack to be resolved. Since Groovy 1.8 we can use the trampoline capability of closures to overcome this problem.

We invoke a trampoline() method on a closure and our original closure is now wrapped in TrampolineClosure instance. Calls to the TrampolineClosure are executed sequentially invoking the original closure, until the original closure returns something else then a TrampolineClosure instance. This way the stack isn't filled and we won't get the stack overflow exceptions.

def sizeList
sizeList = { list, counter = 0 ->
    if (list.size() == 0) {
        counter
    } else {
        sizeList.trampoline(list.tail(), counter + 1)
    }
}
sizeList = sizeList.trampoline()

assert sizeList(1..10000) == 10000

Try with Groovy web console.

1 comments:

trampoline said...

really a piece of brilliant code, you have really talent, good continuation.

Post a Comment