Recursion is a very simple, yet useful and powerful programmer’s tool. A programming routine that activates itself is called recursive. It can be a subroutine or a function. Many programmers often avoid this type of procedure because it can be confusing and complicated. It is often used to solve problems that can be broken down into smaller pieces. These problems can range from quite simple to fairly challenging in nature.
The alternative to recursion is iteration (looping). In general, recursion is sometimes less efficient than iterative solution as far as computer time and resources. However, in many instances, recursion provides a much simpler solution to a complex problem.
When is it Used?
Recursion is for problems that can be defined as a number of sub problems that are similar to the original question. These sub problems must have a known solution that cannot be broken down any further. A perfect example would be file searching. This type of problem would be very difficult with iteration, this is not to say that it can’t be done. With recursion, it is quite easy to check every folder on the hard drive for a particular file as shown below.
Retrieving a web page from a particular site is another excellent example where recursion could save a lot of time. Iteration for this type of problem would be very difficult because there are too many unknown questions. How would the program know if the web page has already been retrieved? What are the limitations the program will have? How far down will the program drill? One domain search at a time only? There are many questions to be asked for a program that uses recursion, but there are fewer questions and better solutions.
Other places that recursion can be used are in the various sorting algorithms as well as finding an item in a sorted list. A recursive procedure could start by checking the item in the center of the list, thereby cutting and eliminating the need to look through half the items. It would continue checking by cutting the remaining portion in half again. The routine would continue dividing the list until a match is found or until it is determined there is no match.
What to watch out for?
If a procedure continues to call itself until the stack space is full, an ‘Out of Stack Space’ error will occur. This procedure is called an ‘unbounded recursion’, one that has no end. The ‘Calls dialog box’ is used to determine the sequence that led to the ‘Out of stack space’ error. (Make sure that limitations are set.) The next step is to try to determine what will cause the routine to end. The program needs to be saved before running it so that if it does lock up you can still run the program after a reboot.
Recursion in Action
The following code uses a very fast algorithm to find a particular word in a sorted list. It requires a search word (sKey), an array of sorted words (vList()), and (iLow) and (iHigh), being the index numbers of the first and last items in the array.
Searching for Files
This procedure will recursively search the entire directory structure starting at a specified point. It will return all matching files with the full path. It requires the FileListBox, named File1, and DirListBox, named Dir1, the TextBox, named Text1, and a CommandButton, named Command1. The File1 and Dir1 can be made invisible to increase the speed of the routine. Search for any file and location by changing the search pattern or the starting folder in the Command1_Click event.
Although recursion looks confusing the first time through, spend some time reviewing a few code examples and in no time you won’t know how you worked without it.
Trevor Edis is a college computer instructor who has been working with computers for the past 15 years. He has gained a reputation as a specialist in Visual Basic and has taught at several colleges. He has developed many business solutions for a variety of companies locally and internationally.