Page 820 - Introduction to Programming with Java: A Problem Solving Approach

786 Appendix 8 Recursion
Factorial
line#
27
factorial
factorial
factorial
factorial
factorial
n
nF
n
nF
n
nF
n
nF
n
nF
output
12
5
?
4
?
27
3
?
27
2
?
27
1
?
23
1
27
2
27
6
27
24
27
120
12
120
Figure A8.2 Trace of Factorial program in Figure A8.1
Figure A8.2 shows a trace of the execution of the program in Figure A8.1. The first call to the factorial method is on line 12 in the main method with an argument of 5. The next four calls to the factorial method is from within the factorial method on line 27 with arguments of 4, 3, 2, and 1. When the parameter equals one, the stopping condition is satisfied, and nF gets assigned the value 1 on line 23. Then, the returning process commences. The 1 from the fifth factorial call returns to the fourth factorial call, which on line 27 multiplies it by 2 and returns 2. This value returns to the third factorial call, which on line 27 multiplies it by 3 and returns 6. This value returns to the second factorial call, which on line 27 multiplies it by 4 and returns 24. This value returns to the first factorial call, which on line 27 multiplies it by 5 and returns 120. This value returns to the argument of the println statement in the main method on line 12, and this statement prints out the computed value. In this problem, all the useful work is done in the return sequence, after the stopping condition is reached.
We included the local variable nF in the program in Figure A8.1 just to give this trace some substance. Hopefully, it helps you visualize the recursive calling that drills down to the simplest case and the subse- quent result accumulation as the nested methods return. In practice, however, experienced programmers would not include the local nF variable. Instead, they would probably write the factorial method like that shown in Figure A8.3.
NoticethatFigureA8.3’simplementationextendsthestoppingconditionton == 0toincludethecase of 0!, which is also equal to unity.
Apago PDF Enhancer
method execution, where the parameter value was 2. That method execution returns 2 * 1 􏰀 2 to the previ- ous method execution, where the parameter value was 3, etc., until it gets back to the original method execu- tion, which returns 5 * 24 􏰀 120, as the value for the argument in the println method called in main.