The Print statements are commented out in the Factorial application. You can remove the apostrophes from in front of them and then run the application to watch the sequence of function calls while the factorial o! a number is being calculated. The first Print statement tells us that a new instance of the function has been activated and gives the number whose factorial it’s about to calculate. The second Print statement tells us that the active function is about to call another instance of itself· and show. which argument it will supply to the function it’s calling. The last Print statement informs us that the factorial function is done. Here’s what you’ll see in the Immediate window if you call the factorial ()function with the argument
Starting the calculation of 4 factorial
calling factorial(n) with n= 3
This list of messages is lengthy, but it’s worth examining for the sequence of events. The first time the function is called, it attempts to calculate the factorial of 4. It can’.t complete its operation and calls factorial(3) to calculate the factorial of • 3, which is needed to calculate the factorial of 4. The first instance of the factorial function is suspended until factoriaI(3) returns its result. Similarly, factorial(3) doesn’t complete its calculations because it must call factorial(2). So far, there are two suspended instances of the factorialO function. In turn, factorial(2) calls factorial(l), and factorial(l) calls factorial(O). Now, there are foui’suspended instances of the factorial() function, all waiting for an intermediate result before they can continue with their”calculations. Figure 11.2 shows this process.
When factorial(O) completes its execution, it prints the following message and returns a result;
Done calculating () factrial
This result is passed to the most recently interrupted function, whiCh is factorial(l). This function can now resume operation. complete the calculation of 11(1 x 1) and then print another message indicating that it finished its calculations. A$ each suspended function resumes operation, it passes a result to the function from which it was called, until the very first instance of the factorial() function fmishes the calculation of the factorial of 4. Figure 11.3shows this process. (In the figure, factorial is abbreviated as/act.)
What Happens When a Function Calls itself
If you’re completely unfamiliar with recursive programming, you’re probably uncomfortable with the idea of a function callingitself, Let’s take a closer look at what happens when a function calls itself. As far as the computer is concerned, it doesn’t make any difference whether a function calls itself or another function. When a function calls another function, the calling function suspends execution and waits for the called function to complete its task. The calling function then resumes (usually by taking into account ariy result returned by the function it called). A recursive function simply calls itself instead of another one. Let’s look at what happens when the factorial in the previous function is implemented with the following line L” which factoriall () is identical to factorialt ( ):
When the factorialt) function calls factorialtf), its execution is suspended until factoriall 0 returns its result, A new function is loaded into the memory and executed. If the factorialf) function is called with 3, the factoriallO function calculates the factorialof2.
.Similarly, the code of the factorial1() function is:
factoriall – n * factoria12(n-l)
This time, the function factorial20 is caned to calcmate the factorial of 1.The function factorialzf) in turn calls factoria13(), which calculates the factorial of zero. The factorial30 function completes its calculations and returns the result 1. This is in turn multiplied by.lto produce the factorial of 1. This result is returned to the function of the factorial of 2,(which is 2″1). ; The value is returned to ‘the factorialO function, which now completes.the calculation of 3 ‘(3*2″0’: 6).
.Recursive Calls and the Operating System
You cart think of a recursive {unction calling itself as the operating system supplying another identical function with a different name; it’s more or less what happeAS. Each time your program calls a function, the operating system does the following
1. Saves the status of the active function
2. Loads the new function in memory
3. Starts exec;utU:tgthe new function
If the function is recursive-in other words, if the new function is the same as the’ one currently being executed=nothing changes. The operating system saves the status of the active function somewhere and starts executing it as if it was. another function. Of course, there’s no reason to load it in memory again because the function is already there. When the newly called funCtionJinishes, the operating system reloads the function it interrnpted in memory and continues its execution. I mentioned that the operating system stores the status of a function every time it must-interrupt it to load another function in memory. The status informiltion includes the values of its variables and the location where execution was interrupted. In effect, after the operating system loads the status of the interrupted function, the function continues execution as·if it was never interrupted. We’ll return to the topic of storing status information later on in the section “The Stack Mechanism.”
Recursion by Mistak
Recursion isn’t as complicated as you may think. Here’s an example of a recursive situation you may have experienced without knowing it Figure 11.4shows a simple application that fills the background of a picture box with a solid color. Instead of setting the control’s BackColor property though, it draws vertical lines from one end of the control to the other. Every time the New Color button is clicked, the Picture- Box control is filled slowly with vertical lines. The color of the lines is chosen randomly. This application is quite similar to the ‘ClrGrads application of Chapter 7, Mtlnipulating Color and Pixels with Vrsual Basic, w!lich ~ the background of the control with a gradient. I used a solid color in this example to simplify the code.
