An often used example for worst, average and best case algorithm analysis in computer science are the Fibonacci numbers, which are defined as fib(n) = fib(n-1) + fib(n-2) with fib(1) = fib(2) = 1. Often a recursive and an iterative algorithm are given to analyze the different performances, with the result that recursions are always bad and should be avoided. I want to show that this is not always true.
The given recursive algorithm generally looks like this:
int fib(n):
return fib(n-1) + fib(n-2)
While the iterative approach may be similar to this one:
int fib(n):
f = f1 = f2 = 1
for i=3 to n:
f = f1+f2
f2 = f1
f1 = f
return f
The question is now, which one is better regarding time consumption. The answer is obvious; while this recursive one starts two sub calls for each n and calculates values doubly, which ends up with O(2n) in Landau notation, the iterative one just calculates the next value based on the predecessors, what would make O(n). The usage of this single sample over and over again gives the impression, that recursions are always baaaad. But with a few tricks we will be able to change that (I must admit that they are only possible with a higher memory usage).
The biggest problem about the recursive solution above is that every call of fib(n-2) will calculated a Fibonacci number, we already know. Let's have a closer look on this. When trying to give us the fifth Fibonacci number, we would do the following:
fib(5) = fib(4) + fib(3)
= fib(3) + fib(2) + fib(3)
= fib(2) + fib(1) + fib(2) + fib(3)
= 1 + 1 + 1 + fib(2) + fib(1)
= 5
In this example, fib(3) is calculated twice, but we only need to do this once, as long space time does not rip and change mathematics. So we use a simple buffer of the size n to cache all our results, and when we calculated a Fibonacci number, we store it in there. With this little trick, we can reduce the algorithm to O(n), just like the iterative one! The code might look like this:
int[n] buffer = {0,0...,0}
int fib(n):
if buffer[n] != 0: //if we calculated that one before, we can skip here.
return buffer[n]
else
return buffer[n] = fib(n-1)+fib(n-2)
Please note that this trick cannot be done with the iterative code, as it does not depend on predecessors of n except of the two it stores itself in f1 and f2.
But we can go even further. For that, let's just expand the formal definition a bit by just plugging itself for n=7.
fib(7) = fib(6) + fib(5)
= fib(5) + fib(4) + fib(5)
= 2*fib(5) + fib(4)
= 3*fib(4) + 2*fib(3)
= 5*fib(3) + 3*fib(2)
= 8*fib(2) + 5*fib(1)
= 8 + 5 = 13
You will notice, that the factors are increasing Fibonacci numbers, while the others decrease. We can use this to meet just in the middle:
fib(n) = { n is odd: fib((n+1)/2)² + fib((n-1)/2)²
n is even: fib(n/2) * (fib(n/2+1) + fib(n/2-1)) }
With this we can reduce the whole recursion to O(n), as we need approx fib(n/2) at every call, which gives us log(n) as depth. As we still need about 2 new calls for each level, we get O(2log n) = O(n). If we add a buffer, we get even more. We then need only 2 (or 3) new calls for every sub call, which are buffered and gives us, summed up, O(log² n).
In the final competition between iterative, recursive with buffer and this own, modified recursive algorithm, the winner for the Fibonacci numbers up to 10000 is clear: (The fact that they do not look exactly look like O(n) and O(log² n) are artefacts from the BigInteger-class I was using, as fib(10000) is a very big number)
