Groovy Functional Programming - Recursion

Consider the following list of numbers.

def numbers = [1, 2, 3, 4, 5]

Iteration

Let's calculate the sum of numbers. First let us approach solution using imperative method

def computeSumImperative(List numbers) {
    def sum = 0
    def iterator = numbers.iterator()
    while(iterator.hasNext()){
        sum += iterator.next()
    }
    sum
}
println computeSumImperative(numbers)

Recursion

Here we are using iterator to get each element in the list and keep accumulating the sum. Typically, I would have used a for each loop(Groovy provides more declarative approaches using internal iterators. More on that for another time). However for each loop is a syntactic sugar over the iterator. Hence I decided to skip it use the underlying iterator directly.

An alternate way of representing a list type is as a combination of head and tail. Head is of scalar type and tail is of a vector type. Hence the list [1, 2, 3, 4, 5] can be expressed as 1 (Head) concatenated with [2, 3, 4, 5]. Similarly list [2, 3, 4, 5] can be expressed as 2 concatenated with [ 3, 4, 5] and so on.

println numbers.head() // 1
println numbers.tail() // [2, 3, 4, 5]

Now let us approach the solution keeping the above structure in mind.

def computeSumRecursive(def head, def tail) {
    if(!tail){
        head
    }
    else{
        head + computeSumRecursive(tail.head(), tail.tail())
    }
}
println computeSumRecursive(numbers.head(), numbers.tail())
// OR to make it work with empty list
println computeSumRecursive(0, numbers) 

You may want to take a look at the slides from my FunctionalConf talk for more examples.