# 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:

**examples/groovy/factorial.groovy**

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:

**examples/groovy/fibonacci.groovy**

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:

**examples/data/dependencies/main.txt**

a b

**examples/data/dependencies/a.txt**

c d

**examples/data/dependencies/b.txt**

d e f

**examples/data/dependencies/e.txt**

f

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

**examples/groovy/list_dependencies_recursive.groovy**

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')