Algorithms can often be implemented recursively or nonrecursively; the decision rests with the programmer, who might shy away from a recursive solution because the algorithm might not terminate or that performance might be poor. In reality, recursion can allow for very elegant code as well as facilitating an interesting and economical type of code reuse.
Iterative algorithms, especially those with a loop, can usually be easily rewritten to use recursive function calls instead of loops. In some cases it’s a bad idea because the iterative version is usually simpler, faster, and uses less memory.
The classical scenario for recursion was search algorithms, factorial calculations, and so on. A well-know algorithmn that uses recursion is Binary Search.
This recursive version checks to see if we’re at the key (in which case it can return), otherwise it calls itself so solve a smaller problem, ie, either the upper or lower half of the array.
int BinarySearch(int iSortedArray[], int iFirst, int iLast, int iKey)
{
if (iFirst <= iLast) {
int iMid = (iFirst + iLast) / 2;
if (iKey == iSortedArray[iMid])
return iMid;
else if (iKey < iSortedArray[iMid])
return BinarySearch(iSortedArray, iFirst, iMid-1, iKey);
else
return BinarySearch(iSortedArray, iMid+1, iLast, iKey);
}
return -(iFirst+ 1); // failed to find key
}
Besides elegant code design recursion can be the reason for some problems.
Recursion isn’t safe in C/C++ because there is no reasonable way to deal with running out of call stack space. Even if you dynamically allocate stack frames from the heap, you still can run out of heap and how do you handle the error then?
You might convert the failed call stack allocation into an exception that unwinds the stack until an out-of-stack exception handler is found, but the problem is that any function in any library called from a recursive routine might be the call that blows the stack.
Fortunately any algorithm that can be written recursively can be rewritten iteratively by keeping a heap-based stack object (and if it can be written completely tail-recursively, you don’t even need a stack). The code might be uglier when written iteratively, but it’s always possible.
You’d defenetly use recusion when you can guarantee two things:
- Each recursive step breaks down the problem into a smaller problem of the same type.
- Each recursive step reduces the problem significantly.
The first is a general rule of recursion. If each step doesn’t break the problem down into a smaller problem of the same type, it’s harder to write a recursive function and guarantee that it will terminate. The second is kinda personal guideline. I generally won’t write a recursive function unless it divides the problem in half with each step. This way I can verify with relative ease that the algorithm will be efficient.
Originally I planted to write this post about anonymous recursion with lambda in c#, but then I decited to describe recursion basics a bit more in detail.
A simple recursive function in c# would be for example:
private static double pow(double var, double n)
{
if(n == 0)
return 1;
else
return var * pow(var, n - 1);
}
Anonymous recursion is a recursion technique that uses anonymous functions.
I got the idea to define a special delegate type for self-applicable functions:
delegate T Pow<T>(Pow<T> self);
The delegate above can be defined like this:
Pow<double> myPow = f => f(f);
myPow(myPow);
When myPow is being applied to itselfwill apply myPow to itself, which will ⦠infinite recursion. While not particularly useful in this setting, the example demonstrates that you can in fact have recursive application in a lambda expression. Now all we have to do is to make it do something useful as it goes, such as call functions recursively.
Recursion is beautiful and lambdas are the ultimate abstraction. But that’s too much for now…I’ll write about that sometime.
Dr Watson has died
