Groovy Functional Programming - Recursion

Consider the following list of numbers.

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


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()
        sum +=
println computeSumImperative(numbers)


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) {
        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.

Show Comments