13.2 M o r e Examples with Simple Variables | 639If we can find a base case, we can write a recursive algorithm. Fortunately, we don’t have to
look too far: 0! is defined in mathematics to be 1.
We can code this algorithm directly as follows:
public static intfactorial(int number)
// Returns the factorial of number
// Assumption: number is greater than or equal to 0
// Note: Large values of number may cause integer overflow
{
if (number == 0)
return1; // Base case
else
returnnumber * factorial(number – 1); // General case
}
Let’s trace this method with an original number of 4.
Call 1:numberis 4. Because numberis not 0, the elsebranch is taken. The returnstatement
cannot be completed until the recursive call to factorialwith number– 1 as the argument has
been completed.
Call 2:numberis 3. Because numberis not 0, the elsebranch is taken. The returnstatement
cannot be completed until the recursive call to factorialwith number– 1 as the argument has
been completed.
Call 3:numberis 2. Because numberis not 0, the elsebranch is taken. The returnstatement
cannot be completed until the recursive call to factorialwith number– 1 as the argument has
been completed.
Call 4:numberis 1. Because numberis not 0, the elsebranch is taken. The returnstatement
cannot be completed until the recursive call to factorialwith number– 1 as the argument has
been completed.
Call 5:numberis 0. Because numberequals 0, this call to the method returns, sending back
1 as the result.
Call 4:The returnstatement in this copy can now be completed. The value to be returned
is number(which is 1) times 1. This call to the method returns, sending back 1 as the result.
Call 3:The returnstatement in this copy can now be completed. The value to be returned
is number(which is 2) times 1. This call to the method returns, sending back 2 as the result.
Call 2:The returnstatement in this copy can now be completed. The value to be returned
is number(which is 3) times 2. This call to the method returns, sending back 6 as the result.
Call 1:The returnstatement in this copy can now be completed. The value to be returned
is number(which is 4) times 6. This call to the method returns, sending back 24 as the result.
factorial(number)
ifnumber is 0
return 1
else
returnnumber * factorial(number – 1)