This chapter is slightly different from the previous ones because it doesn’t ‘ describe specific VlSual Basic techniques or controls. Instead, it introduces a powerful technique for implementipg efficient, compact programs. Recursion is a special topic in computer programming that’s one of the least understood among beginners and even among some advanced programmers. It’s surrounded by an aura of mystery and most BASIC programmers ignore it. The truth is, recursive programming is no more complicated than any other programming approach, once you understand how it works and when to use it. Some readers may think that the material in this chapter is of little use to the average programmer. They are probably right, but there is some valuable information in this chapter. Toward the end of it, you’llieam how to write applications that scan an entire folder and its subfolders. The DirMap application is a customized Wmdows Explorer that you can incorporate in your applications even if you don’t quite understand how it works.
Basic Concepts
Recursive programming is used for implementing algorithms; or mathematical definitions, that are described recursively, that is, in terms of themselves. A recursive definition is implemented by a procedure that calls itself; thus, it is called a recursive procedure.Code that calls functions and subroutines to accomplish a task, such as the following segment, is quite normal:
In the preceding code, the MyPaymentsO function calls the CalculatePayment() function twice to calculate the monthly payments for a car and home loan. ‘There’! nothing puzzling abo~t this piece of code because it’s linear. Here’s what it does:
1. The MyPayments() function suspends execution eaCh time it calls the Calculate Payment () function
2. It waits for the Ca1culatePayment() function to complete its task and return a value.
3. It then resumes execution.
But what if a function calls itself? Examine the following code:
Function Dosomething(n As Integer) As Integer
{other statements}
value – value – 1
If value – 0 Then Exit Function
newValue – DoSomething(value)
(more statements}
End Function
If you didn’t know better, you’d think that this program would never end. Every time the DoSomethingO function is called it gets into a loop by calling itself again and again and it never exits. In fact, this is a clear danger with recursion. It’s not only possible, but quite easy, for a recursive function to get into an endless loop. A recursive function must exit explicitly. In other words, you must tell a recursive function when to stop calling itself and exit. The condition that causes the DoSomething() function to end is met when value becomes zero. Apart from this technicality, you can draw a few useful conclusions from this example. A function performs a well-defined task When a function calls itself, it has to interrupt the current task to complete another, quite similar task. The DoSomething() function can’t complete its task (whatever this is) unless it performs an identical.calculation, which it does by calling itself.
Recursion in Real Life
Do you ever run into recursive processes in your daily tasks? Suppose you’re viewing a World Wide Web page that describes a hot new topic. The pa~ contains a term you don’t understand and the term is a hyperllnk. When you click the hyperlink, another page that defines the term is displayed. This definition contains another term you don’t understand. The new term is also a hyperlink, so you click it and a page containing its definition is displayed. Once you understand this definition, you click the Back button to go back to the previous page where you re-read the term knowing its definition, You then go back to the original page. The task at hand involves understanding a topic, adescription, and adefinition, Every time you run into an unfamiliar term, you interrupt the current task to accomplish another identical task such as learning.another term.
The process of looking up a definition it, a dictionary is similar and it epitomizesrecursion. For example, if the definition of Active page is “Web page s that contain ActiveX controls,” you’d probably have to look up the definition of ActiveX controls Let’s say ActiveX controls are defined as “elements used to build-Active Web pages.” This is a sticky situation, indeed. At this point, you’ either have to interrupt you search and find out what Active Web pages are or look up its definition elsewhere. Going back and forth between these two definitions won’t take you anywhere. This is the endless loop mentioned earlier.
Because endless loops can arise easily in recursive programming> you must be sure that your code contains conditions that will cause the recursive procedure to stop calling itself. In the example of the DoSomething() function, this condition is as follows:
If value – 0 Then Exit Function
The code reduces the value of the variable value by increments of 1 until it eventually reaches 0, at which point, the sequence of recursive calls ends. Without such a condition, the recursive function would call itself indefinitely. Once the DeSomething() function ends, the suspended instances of the same function resume their execution and terminate.
Now, let’s look at a few practical examples and see these concepts in action .
A Simple Example
I’ll demonstrate the principles of recursive programming with a simple example: the calculation of the factorial of a number. The factorial of a number, denoted with an exclamation mark, is described recursively as follows:
n! – n • (n-1)!
The. factorial of n (read as n factorial) is the number n multiplied by the factoria of (n-1), which in tum is (n-I) multiplied by the factorial of (n-2) and so on, until we reach O!, which is 1 by definition.
Here’s the process of calculating the factorial of 4:
For the mathematically inclined, the factorial of the number n is defined as follows:
The factorial is described in terms of itself and it’s a prime candidate for recursive sive Implementatiori.The Factorial application, shown in Figure 11.1, lets you specify the number whose factorial you want to calculate in the box on the left and displays the result in the box on the right. To start the calculations, click the ‘Factorial button.
As long as the argument of the. function isn’t zero, the function returns the product of its argument times the factorial of its argument minus 1. With each successiv. ecall of the factorialO function, the initial number decreases by an increment of 1 and eventually, n becomes 0 and the sequence of recursive calls ends. Each time the factorial() function calls itself, the calling function is suspended temporarily. When the called function terminates, the most recently suspended function
resumes execution. To calculate the factorial of 10, you’d call the factorial() function with the argument 10, as follows:
The execution of the factorial(lO) function is interrupted when it calls factorial(9-). This ‘function is also interrupted when factorial(9) calls factorial(8), and so on. By the time factorial(O) is called, ten instances of the function have been suspended and made to wait for the function they called to finish. When that happens, they resume execution.
Let’s see how this happens by adding a couple of lines to the factorial() function. Open the Factorial application and add a few statements that print the’ function’s status in the Immediate window:
