As a developer, chances are every time you hear recursion mentioned you probably also hear of Fibonacci’s number. And in the same breath you probably hear also of stack overflow 🙂

Because — as you get to learn quickly — if you decide to implement Fibonacci’s number via a recursive function, you end up abusing the call stack on every step, typically to the point where you hit stack overflow before computing Fibonnaci(100).

So you then start looking at non-recursive, sequential implementations of the same Fibonacci series and analyze the complexity of it. And then you think oh wait, I can throw some caching in there to make it actually faster and better and you end up writing a lot of code for something that ultimately is as simple as:

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

but you can’t implement it as such because… stack overflow 🙂

Here’s the thing though — you can do all of that in Groovy just writing “normal” code and using a nice little treasure of the language called memoization.

As a quick recap, this is how you’d write a recursive Java Fibonacci implementation:

public int getFibonacci(int n) {
        if (n == 1) {
            return 1;
        }
        if (n == 2) {
            return 1;
        }
        return getFibonacci(n - 1) + getFibonacci(n - 2);
}

And as pointed out before this runs you into the darned stack overflow exception.

The sequential implementation looks something like this:

public int fibonacci(int number) {
   int fibo1 = 1;
   int fibo2 = 1;
   for (int i = 2; i < number; i++) {
      int fibonacci = fibo1 + fibo2;
      fibo2 = fibo1;
      fibo1 = fibonacci;
   }
   return fibonacci;
}

This eliminates the stack overflow issue but you end up repeating computations and you decide you need to start caching the values of each computation and re-use them and so on.

Now here’s what you would do in Groovy:

class Fibo {
   @Memoized
   int fibonacci(int number) {
      switch(number) {
         case 1: return 1;
         case 2: return 2;
         default: return fibonacci(number - 1) + fibonacci(number - 2);
      }
   }
}

What this does is simply building a cache for you where the result of the method gets cached automatically. First time you call a method with a parameter, the method gets executed and the result gets cached — such that subsequent calls to the method with the same parameter will result the value from the cache to be used rather than employ a full invocation of the method!

You can find out for yourself running a code as the one below which measures the time it takes to execute each method:

void measure() {
   def times = 5
   for( def i = 10; i > 1; i-- ) {
      for( var j = 0; j < times; j++) {
         def start = System.currentTimeMillis()
         def val = fibonacci(i)
         def time = System.currentTimeMillis() - start
         println "Time: $time"
      }
   }
}

The above code computes the Fibonacci number for every number from 1 to 10 in reverse order, at each step calling the method 5 times. You will find out that the first time each method is called it takes a while but subsequent calls execute in nanoseconds.

That is because the result gets cached on first invocation, and then the cached value gets returned rather than execute the method.

As it stands, if you call right away fibonacci(100) you will still have a problem with the damn stack … but if you “warm up” the cache first, it works like a charm:

void measure() {
   for( def i = 0; i < 100; i++ ) {
      fibonacci(i)
   }
}

The above code will step through all numbers from 1 to 100 and compute the Fibonacci number for it — and because the method is @Memoized annotated, it will also cache the value! Which means when you call fibonacci(100) afterwards it will return immediately as all it has to do is retrieve from cache fibonacci(99) and fibonacci(98) and add them!

The memoization doesn’t stop here in Groovy though: since sometimes we don’t have access to the source of the method we are invoking (and as such can’t always annotate a method with @Memoized), Groovy also allows us to invoke memoize() on a closure — so you can do something like this:

def fibonacci = { fibonacci(it-1) + fibonacci(it-2) }.memoize()

And achieve the same.

Oh and one last thing, since you can call memoize() on a closure you can cache any method on any object this way by simply doing:

def closure = { param1, param2, ... paramN -> myObject.myMethod(param1, param2, ..., paramN) }.memoize()

and then simply using closure(param1, param2, ... paramN) instead of myObject.myMethod(param1, param2,...paramN) and benefit from the caching.

Now I’m not saying this is the best way to implement Fibonacci’s series — but if you were to take that route and implement caching for each call in Java, think of all the code you’d have to write for this — all of which comes out of the box with Groovy!