Recursion is a valuable programming technique and when a programming problem requires this technique, nothing else quite works. But there is a hidden trap in recursion that you need to know about: It can eat memory resources like nothing else. Here's what happens.
In brief, a procedure is said to be recursive when it contains a statement that calls itself. The calculation of a factorial is an example of recursion that you often see in books because it's a perfect case where recursion works and it would be very difficult to solve the problem any other way.
The factorial of a number n (written as n!) is defined as:
n * (n-1) * (n-2) * ... * 1
For example, 5! is 5 * 4 * 3 * 2 * 1 or 120. Factorial is used a great deal in mathematical problems, especially probability.
The standard way to calculate a factorial in a program is something like this:
Function Factorial(ByVal number As Long) As Long
If number <= 1 Then
Return (1)
Else
Return number * Factorial(number - 1)
End If
End Function
Notice that the function contains a call to itself. (In bold type.)
An example of code which calls the factorial function is as follows:
Note that the function Factorial eventually terminates when number <= 1 because the logic in that case does not recursively call itself again. If the function has an incorrect test (for example, number = 1), the routine will continue to call itself infinitely and eventually the program will crash because it runs out of memory.
When a procedure calls itself, the compiler must create code that saves the complete "state" of the procedure (the value of variables, primarily) so the procedure can resume at that point later. This happens every time the procedure calls itself and memory gradually fills up with these copies until the whole thing winds down again as the "return" statements start being executed. To make the point clear, let's add an initial statement to our Factorial function that simply serves to use up a big chunk of memory:
Dim a(200, 200, 200) As String
a(1, 1, 1) = Now.ToString
(Note ... The VB.NET compiler is smart. If you don't actually put anything into the array, the compiler realizes that it doesn't have to allocate memory for it!)
To track memory use, we use the System.Diagnostics.Process object:
Dim p As System.Diagnostics.Process = _
System.Diagnostics.Process.GetCurrentProcess
MemoryUse.Text &= _
Format(p.WorkingSet64.ToString("N03")) & vbCrLf
The value of 1 through 15 factorial is shown here. Notice how the memory use by the process rapidly increases. Even with Vista's virtual memory, it's pretty easy to crash this program by forcing Vista to simply run out of memory.
--------
Click Here to display the illustration
Click the Back button on your browser to return
--------
Loss of memory is a real problem when procedures start talking to themselves!
