'No'. How many times have I had heard this word during my algorithms courses? The answer: All those times when I suggested a solution and the teacher said no to my answer. When I talked, he usually wasn't impressed. That was because we were made to understand that Algorithms were the key, but I failed to understand the locks or the 'doors'. What were these algo-keys meant to open?. My dilemma was common one: knowing algorithms didn't necessarily meant I knew when to use them. But I tried my best to learn all the algorithms by memcpy'ing most of them into my brain.
Of particular interest in algorithms is something called recursion. This is akin to induction, which signifies how important recursion is given that proof by induction or reasoning was probably one of the drivers of modern mathematics. Recursion requires us to use previously calculated values and apply simply functions over and over until we reach a last condition.
My best work on recursions was creating customised octrees for handling 100,000+ 3D protein structures to find anomalies in the structure. Each structure was made from a few hundred to thousands of atoms with an atom representing a 3D point in the octree. These had to be done within a few hours as we had many conditions to work with.
Recursion with octrees was easy, as recursion is a natural solution to trees. The main problem I faced was iterating through the nodes to discover features of the surface of the molecule. Once I discovered a good termination condition and decided the condition on which to iterate subsides, the problem was straightforward.
Recently I had to work on a decaying values problem. The solution was already provided but a quick look possibly revealed a flawed solution. The problem could be stated as: there are activities that produce values and activities that use these values. I like to call this a consumer and producer problem but unlike the famous problem with the same name, there is no bound on producer and no need to sync with consumer. Simply taken, at any time, the number of decaying values can be found with a numeric sum. If we have x1, x2, x3, xN producers from 1 to N months (say UTC as the starting point) with each producer producing values from >= 0 and consumers y1, y2, y3, yN from 1 to N months, we can calculate left over points simply by doing SUM for i=1...M [Xi - Yi].
The interesting aspect comes when we consider the decay. The decay can be simplified as a monthly decay. In this case, the solution that came to me immediately was using tables and logically representing value produced by Xi as Xi_1, Xi_2, Xi_3, ..., Xi...d) where d = number of months till decay to death (our case was a decay with integer values). While this is perhaps not that difficult to understand, it does not lend itself to a nice and easy solution, especially if we wish to use only SQL queries to get number of values or values decaying in current month.
The actual solution to this problem was a sum of all producers until d months ago, and to subtract it with all consumers. Take time to consider this. a sum and a subtract. That is all the solution needed. When I saw this solution, I did not believe this was right.
But the solution is indeed correct when recursed from the first month. In this case, values can be stored inside the database table as negative values for decayed and dead values, so all we need to do is add. The best part of this solution is that it can be written in a simple SQL query. A gorgeous report on expiring values/leftover values/to be expiring values can be made with minimal logic.
And that is the beauty of recursion. We have to know the end condition and how each iteration will move but more important we must know these critical hints, such as whether a table can solve the problem, or if a value is dependent on another value, or if some rules create dependency in positive or negative direction.
Recursion requires a thorough breakdown of problem to discover if a recurring part occurs or not. Finding these may be really hard but if we can find something recurring, we may find that our code can be written in few lines and 'magically' appear to work nicely.
A note of caution: recursion if often not the most optimal solution to a problem. In our case, we run each recursive iteration once a month and save the values in database. This allows us to leverage recursion in a very optimal way. However, recursion for something like sequence alignment can be as slow as exponential time while the same solution with tables (dynamic programming) is of order N x M (length of sequences).