SPECIAL ISSUES IN RECURSIVE PROGRAMMING 831

A Real-Life Example

Imagine that you are so disciplined and organized that you can place every document you use in your office on top of a document stack. Every time you’re interrupted by a visitor or a phone call, you leave the document you were working with on top of this paper stack and remove another document from your filing cabinet to work on. When you’ve finished, you take the document in front of you and place it back in the filing cabinet (or if you’re interrupted again, you place this document on the stack and retrieve another one from the filing cabinet).

What you now have in front of you is the document you were working on when you were interrupted. When you’ve finished with this document, you put it back where it belongs and another document surfaces on the stack—the document you interrupted working on to work with another document. After you work with this document, revise it, and put it away, you have another document before you from an even earlier interruption. If you can maintain this type of organization, you’ll never need to waste time looking for documents (and your productivity will be at an all-time high!). Everything will be in its filing space, and most of the time, the document you need will be right in front of you. Thankfully, we’re not as simplistic as our computers, nor do we need to be so rigid. But you’ll probably agree that this type of memory organization makes perfect sense for keeping track of interrupted tasks on your computer.

Special Issues in Recursive Programming

Recursion is not a technique that most programmers regularly use. Only a few situations call for recursive programming, and unfortunately, these programs can’t be implemented otherwise. As the various object models become more and more complicated, you’ll have to implement an increasing number of recursive procedures. The following sections discuss the dangers of recursion and give you a few hints to help you recognize a procedure that calls for recursive programming.

It’s Easy to Write a Never-Ending Program

If you forget to specify an exit condition with a few statements that stop the procedure from calling itself, you’ll end up with a never-ending program, or an endless loop. If this happens, your computer will run out of memory for storing the intermediate results, and the program will end with the “Out of stack space” error message. The memory available for storing intermediate results between procedure calls is limited and it’s easy to exhaust.

The stack isn’t used only for recursive procedures. Each time a function is called, the status of the one that’s interrupted, along with the arguments of the function being called, are stored on the stack. It’s practically impossible to run out of stack space with regular procedures; to do so, you’d have to call an extremely large number of procedures, one from within the other. You can run out of stack space with recursive procedures, though, because you don’t have to write several thousand routines— only one that calls itself and doesn’t provide an exit mechanism.

I’ve tried to produce a stack overflow by calculating the factorial of a very large number. While this was easy with previous versions of VB, this time I’ve exhausted the accuracy of the Long data type before generating a stack overflow. I even changed the Factorial() function’s type to Double to fill the stack, but guess what happened: the string “Infinity” appeared on the form! The ScanFolder() subroutine will never generate a stack overflow, because I can’t imagine a file system with nested folders to a depth of several hundreds.

Copyright ©2002 SYBEX, Inc., Alameda, CA

www.sybex.com

832 Chapter 18 RECURSIVE PROGRAMMING

I had to write a dummy subroutine that calls itself to cause the stack to overflow. After more than 40,000 recursive calls, the stack was exhausted. To be on the safe side, you can catch the StackOverflowException in your code.

Knowing When to Use Recursive Programming

In addition to knowing how to implement recursive programming, you need to know when to use it. The recursive nature of many problems isn’t obvious, so it may take a while to get the hang of it. (We humans aren’t trained to think recursively, but once you’ve established the recursive nature of a problem, the recursive algorithm will follow quite naturally.) An algorithm that, in the middle of carrying out a task, has to start and complete an identical task is a prime candidate for recursive implementation. Consider a procedure for scanning the contents of a folder. First, it counts the files. If the folder has subfolders, the same process must be repeated for each subfolder.

If you find yourself nesting loops in many levels or if you’re trying to set up conditions to exit these loops prematurely, your code would probably benefit from a recursive implementation. Recursion bears some resemblance to iteration, and in some situations, you can implement a recursive algorithm with a loop. The factorial algorithm, for instance, can be easily implemented with a For…Next loop. But there are situations in which iterations won’t help.

Try It!

If you’re interested in recursion and would like to experiment a little, here’s a problem that can be solved both recursively and nonrecursively: Write a program that accepts a phone number and produces all possible seven-letter combinations that match the phone number (vanity numbers, as they are called). This is not a trivial task, no matter how you look at it. There are 3 to the power of 7, or 2,187, possible combinations, because each number can be mapped to one of three letters and phone numbers have seven digits (excluding the area code).

I’ve mentioned already that recursive routines are quite common when programming with classes of .NET Framework. You have already seen a few recursive routines in earlier chapters, and I would like to go through a couple of typical examples presented in earlier chapters. In Chapter 5, you saw a recursive procedure for scanning the items of a menu, and in Chapter 16, you saw a recursive procedure for scanning the nodes of a TreeView control. Now that you have a better understanding of how recursion works, you may wish to take a closer look at these applications. In the following sections, I will focus on the recursive nature of these routines and not on the object models used in each example.

Printing a Menu’s Commands

In Chapter 5, you saw a subroutine that iterates through the items of a menu. If an item leads to a submenu, the submenu’s items are also scanned, and this process is repeated to any depth. Of course, no menu item should be nested in more than two or three levels, but this procedure will work with any menu structure. The following code iterates through the items of a MainMenu object and prints all the commands in the Output window. MapMenu is the name of a button on a form with a menu,

Copyright ©2002 SYBEX, Inc., Alameda, CA

www.sybex.com

SPECIAL ISSUES IN RECURSIVE PROGRAMMING 833

and it prints the names of the commands at the top level. It scans all the items of the menu’s MenuItems collection and prints their captions. After printing each command’s caption, it calls the PrintSubMenu() subroutine, passing the current MenuItem as argument. The PrintSubMenu() subroutine iterates through the items of the collection passed as argument and prints their captions. The MapMenu command’s code is shown here:

Private Sub Button1_Click(ByVal sender As System.Object, _

ByVal e As System.EventArgs) Handles Button1.Click

Dim itm As MenuItem

For Each itm In Me.Menu.MenuItems

TextBox1.AppendText(itm.Text & vbCrLf)

PrintSubMenu(itm)

Next

End Sub

The PrintSubMenu() subroutine, shown in the following code, goes through the MenuItems collection of the MenuItem object passed as argument and prints the captions of its items. If the current item leads to a submenu (in other words, if it has its own MenuItems collection), it calls the PrintSubMenu() subroutine recursively. The PrintSubMenu() subroutine is called with a different argument every time, and this argument is the current menu item—the item whose submenu we want to scan.

Sub PrintSubMenu(ByVal MItem As MenuItem) Static indentLevel As Integer indentLevel += 5

Dim itm As New MenuItem()

For Each itm In MItem.MenuItems TextBox1.AppendText(Space(indentLevel) & itm.Text & vbCrLf) If itm.MenuItems.Count > 0 Then PrintSubMenu(itm)

Next indentLevel -= 5

End Sub

When the PrintSubMenu() subroutine starts executing, it increases the variable indentLevel by 5. This variable is the number of spaces printed in front of each item’s caption. We increase the indentation level by five spaces every time we run into a new submenu, and we decrease it every time we move to the previous menu level. When the PrintSubMenu() subroutine finishes processing a submenu, the indentation is decreased by five spaces, so that items on the same level have the same indentation.

Printing the Nodes of a TreeView Control

Scanning the nodes of a TreeView control is another typical example of a recursive procedure, because each node may have a collection of nodes under it, and this can go on to any depth. For the purposes of our example, we’ll assume that the TreeView control has a single root node. This isn’t an unreasonable assumption, because most tree structures have a single root and you should try to implement trees with a single root node to simplify your code. If you have a tree with multiple root nodes, you must write a loop that iterates through the root nodes, and for each node you must call the ScanNode() recursive procedure.

Copyright ©2002 SYBEX, Inc., Alameda, CA

www.sybex.com