Recursive Programs

I would like to chat about one of my favorite programming topics, implementing recursive algorithms.

Recursion in computer science is a method where the solution to a problem depends on solutions to smaller instances of the same problem. A recursive program is a program that calls itself to work on a smaller sub problem. When the stop condition (last problem) is reached, all results are put together to reach the desired result. The tricky part is to make sure that the program does not execute in a infinite call loop.

I am going to show you how to write a recursive program to perform a summation of the numbers n to m. There are two types of recursion (tail or regular) that can be used to solve the problem.

Tail recursion is when the program passes the intermediate results to the next function call. When the stop condition is reached, the result is fully calculated and just returned off the function call stack. Some compilers are designed to handle this fact and do not incure the costs of stack space to hold the intermediate calls since they are of no value.

Regular recursion is when the program is waiting for a result to be returned from the next function call. With this type of recursion, the result is only fully realized when the first call finishes the final calculation.

The function below solves the summation problem with tail recursion by counting down from m to n on sub calls.

The function below solves the summation problem with regular recursion by counting up from n to m on sub-calls.

It has been mathematically proven that recursive algorithms can be re-written as iterative ones. Constructs such as the FOR or WHILE loop are used in such solutions. However, the solutions are not as elligant as a recursive one.

The function below solves the summation problem by using a loop construct.

The bottom line is that recursive programs take longer to execute than iterative ones. I ran the three alogirthms above to give me a summation from 5 to 1500. The table below shows the run times.

In short, recursive programs use the runtime stack to save context information of each function call which can consume memmory. For large problems, one might run out of memmory due to this fact unless tail recursion with a smart compiler is used. However, the compactness of these algorithms make them appealing and fun to write.

If you are interested in this topic, trying writing programs for the Fibannoci Sequence, Factorial Expressions, or the Tower of Hannoi problem.

As usual, here is the sample code that was used to create recursive summation programs.