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.