Groovy recursive functions

Recursive functions are functions that call themselves.

In many cases using recursive functions greatly simplifies the code we need to write.

For example when traversing some tree-like data structure.

One critical point in every recursive function is that there most be some stop-condition, that will not create further recursive calls. Otherwise we would end up in an infinite deep black hole.

Factorial in recursive

The mathematical expression n! ( factorial) can be defined in the straigh forward way as: 1 * 2 * … * n or in the recursive way:

1!     = 1
n!     = n * (n-1)!

In a similar fashion we can implement the calculation of n! in both ways. The second way is called recursive definition and it is implemented with recursive function calls:

def fact(n) {
    if (n == 1) {
       return 1
    }
    return n * fact(n-1)
}

println( fact(5) )  //     120
println( fact(10) ) // 3628800

What we must not forget is that we need to check for the stop-condition (the n == 1) before the recursive call.

Fibonacci in recursive call

Fibonacci series is usually defined in a recursive formula:

f(1)        1
f(2)        1
f(n)        f(n-1) + f(n-2)

It can be implemented in this way:

def fibo(n) {
    if (n == 1 || n == 2) {
        return 1
    }
    return fibo(n-1) + fibo(n-2)
}

println( fibo(1) )  // 1
println( fibo(2) )  // 1
println( fibo(3) )  // 2
println( fibo(4) )  // 3
println( fibo(5) )  // 5
println( fibo(6) )  // 8

Recursive

For this example we have created an imaginary tree-structure. A dependency tree. Each file lists its dependencies.

We start with the “main” file:

a
b

c
d

d
e
f

f

The script to traverse the tree in a recursive fashion is this:

root = '../data/dependencies/'

def list_dependencies(name) {
    def path = root + name + '.txt'
    def fh = new File(path)
    if (! fh.exists()) {
        return
    }

    def reader = fh.newReader()
    while ((line = reader.readLine()) != null) {
        println(line)
        list_dependencies(line)
    }
}

list_dependencies('main')

timestamp: 2019-04-16T16:30:01 tags:

• def