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 = lngResultEnd 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 IfEnd 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 IDENTITYParentCategoryID intCategoryName  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.