Recursive Algorithm

Now that we’ve looked at what an algorithm is, we can go a bit deeper and take on one of the most common section of algorithms: Recursion

Recursive algorithms are actually quite easy to understand and we often use it intuitively in our daily life. Recursion only means, that a function calls itself. To illustrate things, we’ll be taking the calculation of the Fibbonaci numbers as an example. The following image shows the first few numbers and a mathematical definition:

So as you see the function f has one initial values for n = 0 and n = 1. For every other n, we call the function f recursively.
Since we as programmers are not that interested in the mathematical terms, here goes a very easy and straight forward implementation:

unsigned int f(unsigned int n) {
     if(n == 0 || n == 1)
         return 1;
     else
         return f(n-1)+f(n-2);
}

As you see it nearly matches the mathematical definition after all. If we now were to test this function, we’d soon notice how long it takes to figure out for example n = 50. So how do we make it faster? To answer that question, we’ll first have to take a look at why the algorithm is so slow and for that we need to take a closer look at how applications work in general.

Every application gets a memory area with fixed size, aka as stack, on which it does all its local operations. For every recursion we’re making, all the currently active variables, states, etc. have to be saved onto the stack and only then the “content” for the new function will be loaded. Doing this a few thousand times will crush your performance and can essentially even lead to stack overflows, which means your application will crash.

One way to fix this, is to trade some memory for performance. The main problem of the recursive algorithm is, that it will calculate the same number over and over again. You’ll end up with a tree which is built with the same sub-trees all over again:

With the acquired knowledge we can turn the whole algorithm around and instead of starting at the top, we start at the bottom, save every result in between and then apply the formula for n+1. Now we can immediately look up what the result for any n-i is, we only had to calculate it once and we don’t need to recursively call the function.

#include <vector>
unsigned int f(unsigned int n) {
     std::vector<unsigned int> mem(n+1, 0);
     mem[0] = 1;
     mem[1] = 1;
     for(unsigned int i = 2; i < n+1; ++i)
         mem[i] = mem[i-1] + mem[i-2];
     return mem[n];
 }

You can obviously also use an array if you’d like, but I prefer to use modern containers, which should also assert for out of bound mistakes. The pre-allocation of the vector will give us a bit a better performance due to the fact that, vector won’t have to resize itself while inserting new numbers, but in comparison to the recursive algorithm this won’t be noticeable anyways.

Although this might seem to have worked just for this specific case, the used principles can be applied to quite a few recursive algorithms and is called memoization (no it’s not memorization). Here are the steps again:

  1. Find the recursive formula.
  2. Implement a straight forward algorithm.
  3. Bottom-Up the algorithm and ‘memo(r)ize’ all the steps.

Keep in mind though, that this method is just one way to optimize algorithms and that it might work for other problems, but not be the best way to do it.

I hope my article wasn’t too unstructured and confusing, but gave you some insight or refreshment on that topic.
A complete example with benchmarking can be found on GitHub.

What are Algorithms?

Although I guess most of you know exactly what an algorithm is, I felt anyways that I needed to give a small definition, before I’ll be able to cover specific (types) of algorithms.

When dealing with problems in computer science one generally looks at the ‘theory’ behind solving the problem and the actual implementation separately. Thus an algorithm can informally be defined as the way/idea on how to solve a certain problem, but it often won’t contain an actual implementation to keep a very general layer.

A formal definition of what an algorithm is, can be quite philosophical and complex and is only needed, if you for example have to prove that there doesn’t exist an algorithm for a given problem. Anyways I won’t be going any deeper on that topic and I often won’t stay very general and will give C++ implementations to most of the algorithms.

The course at the university is in fact called “Algorithm and Datastructures”, thus you can imagine that I’ll be also looking at different datastructures. In essence are datastructures also algorithm; they solve the problem of efficiently storing and retrieving data and make use of various other algorithms for their implementation (i.e. a heap sorts its node in a certain way, as describe by an algorithm).

All in all not a very interesting or in-depth article, but it seemed important anyways. Of course if you’re all about knowledge go read the Wikipedia article and start click your way from there into the wildness of the internet.

Stay tuned for further updates! :-)