If you are a fledgling programmer, you may have heard the word "recursion", and be wondering what it means. Recursion put simply, is when a sub-routine in a program calls itself during the course of that same sub-routine's execution.
This causes the sub-routine to start over from the top of it's algorithmic definition, causing a loop in the program. Think of recursion as a looping structure, that exists without using any of the normal looping commands to set up the loop. Just like any other loop, there must exist an exit condition to eventually end the recursive looping.
Recursion is the basis for one of the fastest sorts out there, which is known as the QuickSort routine. The QuickSort routine uses recursion, and partitioned sorting to sort arrays, lists, or just about any alphanumeric data structure very quickly.
A long time ago, I converted an old Pascal QuickSort routine to Visual Basic 5.0, and the article I wrote then, explaining how it works, makes an excellent example of how recursion is done.
Recursion is best used when no clear cut loop counter starting at one value, and incrementing to another, can be established. Rather, an exit condition will usually exist, which does not depend on a set number of times through a loop occurring to become satisfied.
As the recursive routine calls itself over, and over, it builds up a set of instances of itself, none of which has satisfied the exit condition, but which do a small part of the work of accomplishing that condition each. The instances build until the last one called experiences the exit condition.
Once this predetermined exit condition occurs, the recursive routines "fall out of" all of the previously called instances of themselves in turn, thereby ending the recursive looping. This condition could be having an array sorted, or finding a certain instance of a search term in a page, paragraph, or other data structure.
Keep in mind that there are many other uses for recursion, with the QuickSort routine being just one of them. Be sure to add recursion to your programming bag of tricks, as it can be a real problem solver.
Like this page? Link to it from your own website; just copy/paste this HTML:
