agillo.net | about me

Getting groovy with Fibonacci

After reading an article on Memoization I had a little fun with the Fibonacci sequence in groovy to try it out. As a developer Fibonacci is probably well known to you. Not because it serves any practical value, but because of its tendency to pop up as the defacto example on closures or during interview questions.

As a quick reminder it goes 1, 1, 2, 3, 5, 8 with every subsequent number being the sum of the previous 2. since we have to start somewhere the sequence defines(hardcodes) that the 0th item is 1 and the 1st item is also 1.

Below is the recursive code:

def fib(n) {
  if (n<2) return 1
  else return fib(n-1) + fib(n-2
}

or the equivalent shorthand

def fib(n) {n<2 ? 1 : fib(n-1)+fib(n-2)}

Which produces

fib(30) // 1346269 (23.587 seconds)
fib(300) // stackoverflow

Well that works but unfortunately with a pretty ridiculous runtime. The reason being that the compiler is doing a lot of redundant work. We have hardcoded the results for fib(1) and fib(2) but everything else is recalculated every time. For a simple case like fib(6) look at all the redundant recalculations. In fact apart from fib(5) there isn't a calculation we don't do twice

This is where memoization comes in. In essence the first time we come across a new calculation like fib(3) we are going to store the answer, or memoize it. You could do this easily with a hashmap but groovy provides a built in memoize feature

def mem;
def fib = {n<2 ? n : mem(n-1)+mem(n-2)}
mem=fib.memoize()

Which gives

fib(30)  // 1346269 (0.026 seconds)
fib(300) // stackoverflow

From 23 seconds to 0.026 seconds!

Unfortunately when I ran it for a big number like fib(300) it still crashes with a stackoverflow exception. So I rewrote it again in a non recursive style, with a little Fibber object that basically moves along the fibonacci sequence.

class Fibber {
  def old=1,fib=1,current=1

def next() { def newFib=fib+old old=fib fib=newFib current++ } }

def fib(n) { def fibber = new Fibber(); while(fibber.current < n) fibber.next() return fibber.fib }

which gives

fib(30) // =1346269 (0.013 seconds)
fib(300) // =35957932520658356096176566517218909905236... (0.018 seconds)
fib(3000) //=Huuuuuge number (0.135 seconds)

So this is faster and allows for much larger numbers. It kind of makes me wonder what the benefit of optimizing with memoisation really is. Sure I like the recursive style, its very elegant but if you're going to optimize it perhaps just go all the way and use a non recursive function?

Maybe there are better examples than fibonacci to use memoization. Anyone know of instances where recursion is going to end up being a more performant solution?

blog comments powered by Disqus