Recursive Programming
This page describes a programming technique called Recursive Programming,
in which a procedure calls itself repeatedly until some escape condition is met.
Recursive programming is a powerful technique that can greatly simplify some programming tasks. In summary,
recursive programming is the situation when a procedure calls itself passing in a modified value of the parameter(s) that was passed
in to each iteration of the procedure. Typically, a recursive programming environment contains (at least) two procedures: first, a procedure
to set up the initial environment and make the initial call to the recursive procedure, and second, the recursive procedure itself
that calls itself two or more times.
Let's begin with a simple example. The factorial of a number N is the product of all the
integers between 1 and N. The factorial of 5 is equal to 5 * 4 * 3 * 2 * 1 = 120. In the real world you
would not likely use a recursive procedure for this. Instead, you would use a function like the following:
Function Factorial(Num As Long) As Long
Dim N As Long
Dim R As Long
R = 1
For N = 1 To Num
R = R * N
Next N
Factorial = R
End Function
However, the Factorial is a simple yet instructive example of how recursion works. This example will use two procedures. The
StartFactorial procedure sets up the recursion and the
Fact procedure uses recursion
by calling itself to calculate the factorial. The
StartFactorial procedure is shown below:
Sub StartFactorial()
Dim F As Long
F = Fact(5)
Debug.Print "F: " & CStr(F)
End Sub
The
StartFactorial procedure calls the function
Fact procedure, passing it a value
of 5 and then displays the result. The
Fact procedure calls itself recursively to calculate the actual
factorial of 5. The
Fact procedure is shown below. The
Fact function uses
a
Static variable to hold the results between each call to the
Fact procedure.
STATIC VARIABLE -- A Static variable, declared with the Static keyword, is a variable within a procedure
that retains its value between calls to the procedure that contains the variable. Normal variables are destroyed when the procedure
that contains them terminates and are initailized to their defualt values when the procedure is called subsequently. A static
variable, however, retains its value even after the procedure ends. In a way, a Static variable is like a global variable, except that
the scope of a static variable is within the containing procedure only. That is, even though the static variable retains
its value after the procedure ends, you can access (read or write) the variable only from within the procedure in which it is declared.
The following code in Fact
If R = 0 Then
R = 1
End If
is used to initialize the variable
R to 1 the first time
Fact is called. If we did
not do this, the first time
Fact is called, the variable
R will be 0 and thus the
result of the function will be 0 since 0 times any number is 0. By initializing
R to 1, the multiplication
will work properly. This initialization code also ensures that the Factorial of 0 is properly calculated as 1. The code will return
a value of 1 for the factorial of a negative number. This is mathematically incorrect, as the factorial of a negative number is
undefined. We will leave the code as is for simplicity, but if you were to use this code in a real-world application, you would want
to ensure that the input parameter is greater than or equal to 0 and return some error indication to the caller.
Function Fact(N As Long) As Long
Static R As Long
If R = 0 Then
R = 1
End If
If N > 1 Then
R = R * N * Fact(N - 1)
End If
Fact = R
R = 1
End Function
This line of code highlighted in yellow is the actual recursive call, in which Fact calls itself. As you
can see, this line in the procedure Fact calls itself, passing to itself the value (N - 1),
a value 1 less than the input parameter. When Fact runs again recursively, it calls itself passing a value
1 less than its input value. Fact continues to call itself as long as the value of
N is greater than 1.
Let's step through the path of execution of the Fact function. The StartFactorial
procedure first calls Fact passing in a value of -1. This causes the value R to
be initialized to a value of 1. Without this initialization, the first time Fact is called, R
would be 0, and the result would be 0 since multiplying any number by 0 results in 0. This initialization is required only when
Fact is called for the first time. On subsequent calls to Fact, the variable
R is 1, the value to which it is set in the last line of code in the procedure.
Then, StartFactorial calls Fact passing it a value
of 5. Since this is greater than 1, the value R is set to R * N, or
1 * 5 and then the procedure Fact is called with a value of N - 1
or 4. This causes Fact to be called again with a value of 3, which calls it again with a value of 2. All of
these results are multiplied together, 5 * 4 * 3 * 2 giving a result of 120. We do not call Fact
when N is 1, since multiplying by 1 does not change the result. The code would work properly, however, if we called Fact
with a value of 1, but it is unnecessary to do so and only adds unnecessary overhead to the function.
While recursive programming is a powerful technique, you must be careful to structure the code so that it will terminate properly when
some condition is met. In the Fact procedure, we ended the recursive calls when N was
less than or equal to 1. Your recursive code must have some sort of escape logic that terminates the recursive calls. Without such
escape logic, the code would loop continuously until the VBA runtime aborts the processing with an Out Of Stack Space error.
Note that you cannot trap an Out Of Stack Space error with conventional error trapping. It is called an untrappable
error and will terminate all VBA execution immediately. You cannot recover from an untrappable error.
For example, consider the following poorly written recursive procedure:
Function AddUp(N As Long)
Static R As Long
If N <= 0 Then
R = 0
End If
R = AddUp(N + 1)
AddUp = R
End Function
In this code, there is no condition that prevents
AddUp from calling itself. Every call
to
AddUp results in another call to
AddUp. The function will continue to
call itself without restriction until the VBA runtime aborts the procedure execution sequence.
See also Recursion And The File System Object for additional recursive code examples.
This page last updated: 14-September-2007