October 22, 2018
Hot Topics:

# Understanding Recursion

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.

 ```Function Search(sKey As String, vlist As Variant, iLow As Integer, iHigh As Integer) Dim iMiddle As Integer 'determine the middle of the range iMiddle = (iLow + iHigh) / 2 'check for a match If StrComp(vList(iMiddle), sKey) = 0 Then 'return index of matched value Search = iMiddle 'is match in upper half of list? ElseIf StrComp(sKey, vList(iMiddle)) > 0 Then 'new low is middle + 1, high remains the same Search = Search(sKey, vList, iMiddle + 1, iHigh) 'match must be in lower half of list Else 'new high is middle -1, low remains unchanged Search = Search(sKey, vList, iLow, iMiddle - 1) End If End Function ```

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.

 ```Private Sub Command1_Click() Call FindFiles("*.doc", "c:\") End Sub Sub FindFiles(sPattern As String, sCurrDir As String) 'check for backslash, add if necessary If Right\$(sCurrDir, 1) <> "\" Then Dir1.Path = sCurrDir & "\" Else Dir1.Path = sCurrDir End If 'loop through current directory listing. For i = 0 To Dir1.ListCount 'listcount returns the total number of number 'items, while listcount - 1 is the last item If Dir1.List(i) <> "" Then DoEvents 'recursively call routine with new current directory Call FindFiles(sPattern, Dir1.List(i)) Else 'sCurrPath equals Dir1.path without the backslash If Right(Dir1.Path, 1) = "\" Then sCurrPath = Left(Dir1.Path, Len(Dir1.Path) - 1) Else sCurrPath = Dir1.Path End If File1.Path = sCurrPath 'assign a pattern to limit displayed files File1.Pattern = sPattern 'check if folder contains files If File1.ListCount > 0 Then 'loop through files in current directory For ii = 0 To File1.ListCount - 1 'display matching files path and file name in text box Text1.Text = Text1.Text & sCurrPath & _ "\" & File1.List(ii) & vbCrLf Next ii End If 'get length of Dir1.Path iLen = Len(Dir1.Path) 'find location of last backslash from the right Do While Mid(Dir1.Path, iLen, 1) <> "\" iLen = iLen - 1 Loop 'remove last portion of the path if necessary Dir1.Path = Mid(Dir1.Path, 1, iLen) End If Next i End Sub ```

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.

Comment and Contribute

(Maximum characters: 1200). You have characters left.

## Enterprise Development Update

Don't miss an article. Subscribe to our newsletter below.

By submitting your information, you agree that developer.com may send you developer offers via email, phone and text message, as well as email offers about other products and services that developer believes may be of interest to you. developer will process your information in accordance with the Quinstreet Privacy Policy.

## Most Popular Developer Stories

Thanks for your registration, follow us on our social networks to keep up-to-date