|
|
|
|
|
|
|
and n - 1 as parameters. Execution of Call 1 pauses until an answer is sent back from this recursive call. |
|
|
|
|
|
|
|
|
Call 2: x is equal to 2 and n is equal to 2. Because n is not equal to 1, the function Power is called again, this time with x and n - 1 as parameters. Execution of Call 2 pauses until an answer is sent back from this recursive call. |
|
|
|
|
|
|
|
|
Call 3: x is equal to 2 and n is equal to 1. Because n equals 1, the value of x is to be returned. This call to the function has finished executing, and the function return value (which is 2) is passed back to the place in the statement from which the call was made. |
|
|
|
|
|
|
|
|
Call 2: This call to the function can now complete the statement that contained the recursive call because the recursive call has returned. Call 3's return value (which is 2) is multiplied by x. This call to the function has finished executing, and the function return value (which is 4) is passed back to the place in the statement from which the call was made. |
|
|
|
|
|
|
|
|
Call 1: This call to the function can now complete the statement that contained the recursive call because the recursive call has returned. Call 2's return value (which is 4) is multiplied by x. This call to the function has finished executing, and the function return value (which is 8) is passed back to the place in the statement from which the call was made. Because the first call (the nonrecursive call in main) has now completed, this is the final value of the function Power. |
|
|
|
|
|
|
|
|
This trace is summarized in Figure 19-2. Each box represents a call to the Power function. The values for the parameters for that call are shown in each box. |
|
|
|
|
|
|
|
|
What happens if there is no base case? We have infinite recursion, the recursive equivalent of an infinite loop. For example, if the statement |
|
|
|
|
|
|
|
|
were omitted, Power would be called over and over again. Infinite recursion also occurs if Power is called with n less than or equal to zero. |
|
|
|
|
|
|
|
|
Figure 19-2
Execution of Power(2, 3) |
|
|
|
|
|
