def fib(position) { if (position 2) BigInteger.ONE else fib(position - 1) + fib(position - 2) } It’s a direct implementation of the recursive algorithm in Groovy. Since the values in the series would grow bigger than an integer or long can hold, we need to use BigInteger for the series values. Due to the dynamically typed nature of Groovy, the only impact of that decision is in the return where BigInteger is used in code: pretty low ceremony. Let’s create a function to help measure the execution time for various position values. def timeit(position, function) { def start = System.nanoTime() def result = function(position) def end = System.nanoTime() def time = String.format("%.2f sec", (end - start)/1.0e9) println "Fib($position): $result, time: $time" } The timeit function receives a position and a reference to a function—a closure—as a parameter. It forwards the position to the closure and reports the time it took to execute. We have everything in place to try out the simple recursion. We’ll start with a small position value first. timeit(5) { position - fib(position) } We called the timeit function and passed it two arguments, a position value of 5, and a closure that receives the position and invokes the fib function. The value at the given position in the Fibonacci series and the time taken is reported by this call. Fib(5): 8, time: 0.02 sec The result is correct and the code took about two hundredths of a second to run. Let’s increase the input to a position of 40 and see how this code performs. timeit(40) { position - fib(position) } The value and the time reported are: Fib(40): 165580141, time: 20.01 sec That took well over twenty seconds: that’s long. But this algorithm will get worse rapidly due to the exponential time complexity. For example, let’s increase the position just slightly by 2. timeit(42) { position - fib(position) } Here are the value and time reported: Fib(42): 433494437, time: 50.42 sec A small variation in the input size but a large degradation in performance. PragPub January 2013 18