|
|
|
|
|
|
|
int Factorial ( /* in */ int n )
// Precondition:
// n >= 0
// Postcondition:
// Function value == n!
// Note:
// Large values of n may cause integer overflow
{
if (n == 0)
return 1; // Base case
else
return n * Factorial(n - 1); // General case
} |
|
|
|
|
|
|
|
|
Let's trace this function with an original n of 4. |
|
|
|
|
|
|
|
|
Call 1: n is 4. Because n is not 0, the else branch is taken. The return statement cannot be completed until the recursive call to Factorial with n - 1 as the actual parameter has been completed. |
|
|
|
|
|
|
|
|
Call 2: n is 3. Because n is not 0, the else branch is taken. The return statement cannot be completed until the recursive call to Factorial with n - 1 as the actual parameter has been completed. |
|
|
|
|
|
|
|
|
Call 3: n is 2. Because n is not 0, the else branch is taken. The return statement cannot be completed until the recursive call to Factorial with n - 1 as the actual parameter has been completed. |
|
|
|
|
|
|
|
|
Call 4: n is 1. Because n is not 0, the else branch is taken. The return statement cannot be completed until the recursive call to Factorial with n - 1 as the actual parameter has been completed. |
|
|
|
|
|
|
|
|
Call 5: n is 0. Because n equals 0, this call to the function returns, sending back 1 as the result. |
|
|
|
|
|
|
|
|
Call 4: The return statement in this copy can now be completed. The value to be returned is n (which is 1) times 1. This call to the function returns, sending back 1 as the result. |
|
|
|
|
|
|
|
|
Call 3: The return statement in this copy can now be completed. The value to be returned is n (which is 2) times 1. This call to the function returns, sending back 2 as the result. |
|
|
|
|
|
|
|
|
Call 2: The return statement in this copy can now be completed. The value to be returned is n (which is 3) times 2. This call to the function returns, sending back 6 as the result. |
|
|
|
|
|
|
|
|
Call 1: The return statement in this copy can now be completed. The value to be returned is n (which is 4) times 6. This call to the function returns, sending back 24 as the result. Because this is the last of the calls to Factorial, the recursive process is over. The value 24 is returned as the final value of the call to Factorial with an actual parameter of 4. Figure 19-3 |
|
|
|
|
|