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:

or the equivalent shorthand

Which produces

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

Which gives

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.

which gives

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?