Most likely, if you are active in the world of computer programming you’ve heard of recursive algorithms. However, even if you haven’t, it becomes obvious what a great tool any programmer can find in recursion. If the idea of recursion had never been created, writing an algorithm that checks if an input string is a palindrome would have to use much more complex (but not nearly impossible) set of steps. If the length of the input string is indeterminate, things can get hairy pretty fast.

     What we’ve learned here is that it is usually not necessary to use recursion on the simpler problems in computer science, but the algorithms defined recursively are substantially easier to write, understand, and check. Recursive algorithms can usually be written with very few statements in a very eloquent fashion. Due to the fewer lines of code, it is often easier to understand and easier to error check.

     Pretty much a recursive algorithm is simply a method or program (or set of steps) that uses a recursive definition of a problem to solve it. Such examples of recursive algorithms are palindrome/password/string checking programs, recursive sorting, recursive function calculators (Ackermann/Fibonacci/factorial), or compilers (as mentioned earlier). We will first make some recursive algorithms for the previously created recursive definitions, and then make another from scratch.

     First let us look at a pre-made algorithm, test it, convince ourselves its true, and then find out why. The following programs are written in pseudo-code by someone who knows java, but it should be applicable to c++ and other high-level languages.

     So, where does this algorithm come from, and does it fit with our recursive definition of the factorial function? We can see from the first part of the if statement that if the function is called to find 0!, 1 is returned, as was outlined in the base case. However, if it is called to find n!, it calls fact(n-1) (factorial of a slightly smaller number) and multiplies that value (once it is returned) by n, and returns that value. This seems to fit with the definition we gave for the factorial function, in fact, if we follow the code and the recursive method calls through, we see a pattern exactly matching the flow that was given earlier in the section on how recursion works.

     Well, that’s just fantastic. But how do we derive a recursive algorithm from a recursive definition? Well, that’s too freaking bad then, isn’t it, because I’m not going to tell you. Oh, what the heck, I guess I might as well not stop now.

     Let’s turn our definition for palindromes into an algorithm that checks an input string to see if it is indeed a palindrome. We know that our base case is a string of length 0 or 1, which will return true, to represent that these base cases are palindromes. Each iteration of the recursive method will pass a string that is two characters shorter to a clone of the function. Also, the two characters on either side must be tested for equality. Therefore, we get: if the first character equals the last character of the string, and the substring excluding these two characters is a palindrome, then we are looking at a palindrome.

     This function could stand to be streamlined a little bit, but it is much simpler to understand and write than the possible direct implementation. The above algorithm will continue to call recursive clones of itself to check smaller inner sets of characters to see if they are palindromes by the inductive rules we defined earlier. This will continue to happen until we reach one of the base cases, at which point, approximately n/2 return statements are executed as the cases are closed and the final answer is reached. If you go through all of the recursive method calls, you will see that the method will continue to open smaller versions of itself many, many times for a large string, until it finally reaches the base case. This is the main downside of recursive algorithms, as they can be very hard to compute for large n (as the computer starts to run out of ram), while a direct algorithm usually takes constant or much smaller time.

Experiment a little with the following palindrome checker.

     This algorithm is exceptionally complex, and overly confusing. Some highly informed people believe after tedious research that Ackermann died from thinking too hard about why he made this function. By some highly informed people, I of course mean me, and by tedious research, I mean a random guess.

     However, underneath the outward appearance of a confusing and useless recursive function, lies a really complex and confusing useless recursive function. But as is often the case, we need create a recursive algorithm for it anyway. Firstly, we should notice that we have 3 base cases. Usually it would be wise to wonder why we would need so many base cases, but the fourth case in Ackermann’s function makes multiple calls to itself, and all the base cases end up being requisite for the function’s termination. Following this function can be quite difficult, as with an m of around 3 or greater, you already have to deal with a tree of sub-calls. We will deal more with the complexity of this function in the next section. For now we say hurrah!, because we don’t need to be able to follow the complex sub-calls of this recursive function, unless it is to appreciate how nice it is to have a computer do it for us. The growth of this function as inputs m and n get larger, is very steep, and that is why we should be happy we can write computer algorithms to solve such problems using brute force (of sheer calculation magnitude and speed).

The definition given for the function above lends itself quite easily to translation into algorithm. The following is one possibility:

This code can start to take a high level of execution time, given even somewhat large m and n. If m exceeds even around 10, some computers will suffer a stack overflow error. As you could imagine, it would eventually become very tedious to calculate by hand.