Recursion - Computer Science Week

Another concept in computer science is that of recursion. Recursion is defined as "repeated application of a rule", but that's not quite accurate. Recursion is the ultimate in "divide and conquer".

A recursive algorithm consists of two parts. The "divide" part turns a problem into two (or more) simpler problems, and the "conquer" part solves the most basic case for the problem. They are an alternative to "iterative" algorithms, which solve a problem by performing the same simple steps over and over. An example of a recursive algorithm is the "merge sort". To sort a list of names in alphabetical order we can do the following:

If the list has one item in it, it is sorted. we are done.
Otherwise, split the list in 2 parts, sort each part and merge the two sorted lists.

Recursive algorithms generally require more memory and computing resources than iterative ones, but they are great for today's supercomputers which have many CPUs, because each one of the "simple" problems can be computed in parallel on a separate CPU. So even though more resources are involved, the problem can be solved faster.

When the last step in the recursive algorithm is the "go do the simpler problem" part, the algorithm is called "tail recursive". Tail recursive algorithms can be transformed (often automatically by today's tools) into iterative algorithms, which makes them more suited to single CPU computers, where resources are limited and running in parallel isn't an option anyway.

Posted in: computing