Login | Register   
LinkedIn
Google+
Twitter
RSS Feed
Download our iPhone app
TODAY'S HEADLINES  |   ARTICLE ARCHIVE  |   FORUMS  |   TIP BANK
Browse DevX
Sign up for e-mail newsletters from DevX


advertisement
 

Recurses! Foiled Again!

This 10-Minute Solution is an explanation of basic recursion techniques in Visual Basic.


advertisement
ne of the terms that strikes terror into the hearts of Computer Science 101 students is recursion. Until you are able to think recursion through, the implications of it are truly frightening. Once you understand it, however, it's a useful tool which allows you to perform tasks that would otherwise be difficult to accomplish.

Simply put, recursion is a process by which a piece of code calls itself over and over again. While this initially sounds like an infinite loop, the difference is that eventually a recursive routine reaches a base case. A base case is a condition which indicates that the code should simply return and not call itself again.

To use a more concrete example, let's examine the process of obtaining a factorial of a number. A factorial, if you don't remember, works like this: 5 factorial (written as 5!) is equal to 5 x 4 x 3 x 2 x 1, or 120. You can perform this function with the following code:



Function FactorialTheBoringWay(intNumber As Long) As Long Dim i As Integer Dim lngResult As Long lngResult = 1 For i = 2 To intNumber lngResult = lngResult * i Next i Factorial = lngResult End Function

Calling this function with 5 returns the correct result of 120.

Using a recursive method means that we have to determine our base case. To correctly calculate the factorial, we want to stop when the value of the number reaches one, since multiplying the total by zero would then create a zero result. Take a look at this code:

Function FactorialRecursively(intNumber As Long) As Long If intNumber = 1 Then FactorialRecursively = 1 Else FactorialRecursively = intNumber * FactorialRecursively(intNumber - 1) End If End Function

You start the recursion in the same way, by calling the function with the value 5:

MsgBox FactorialRecursively(5)

Tracing through this, you end up with a call stack that looks like this:

FactorialRecursively(5) FactorialRecursively(4) FactorialRecursively(3) FactorialRecursively(2) FactorialRecursively(1)

When the number reaches 1, we simply return a value of 1. This causes the function to exit and work its way back up the call stack. The end result is the same: 120.

A more interesting implementation of recursion comes into play if you want to pick data from a hierarchical list. On a recent application, I had to provide a choice of category to the user. The list was hierarchical, with each category maintaining a foreign key to its parent. This was a perfect chance to use some recursion to build a combo box with all the categories. The combo box was then indented a bit to show the hierarchy. The table structure was simple:

CategoryID int IDENTITY ParentCategoryID int CategoryName varchar(50)

If the category was a root level category, I stored a -1 in the ParentCategoryID field. The process of building the list was begun by looping through all the categories where the parent was -1. After adding a category, I then called the function again with the same category ID. This started the recursion and continued until EOF was reached on a category's child categories. To properly process the right-indent, we passed along a variable that indicated how far to indent. Each recursion incremented this value by one. Finally, the database connection was passed as an additional argument to the recursive function. The code is available here, and you can create your own database using the design above.



   
Eric Smith has been a senior consultant with Andersen Consulting, specializing in client/server development using Oracle and Visual Basic, and was senior content developer (Visual Basic) at inquiry.com before it was purchased by Fawcette Technical Publications. He joined the Information Strategies team in September 1997 and is now an independent consultant. He has written or contributed to "Visual Basic 6 Bible" (IDG Books Worldwide, 1998), "Using Visual Basic 6" (Que), and "Inside VBScript with ActiveX" (New Riders Press, 1997). He is certified in Visual Basic 5.0 and Windows Architecture (1 and 2). Reach him here.
Comment and Contribute

 

 

 

 

 


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

 

 

Sitemap