RECURSION - Java Programming: From Problem Analysis to Program Design - page 876

24

fact(4)

fact(4) = 24

num 4

because num != 0
return 4 * fact(3);

return 4 * 6

fact(3)

fact(3) = 6

num 3

because num != 0
return 3 * fact(2);

return 3 * 2

fact(2)

fact(2) = 2

num 2

because num != 0
return 2 * fact(1);

return 2 * 1

fact(1)

fact(1) = 1

num 1

because num != 0
return 1 * fact(0);

return 1 * 1

fact(0)

fact(0) = 1

num 0

because num is 0
return 1;

return 1

FIGURE 13-1 Execution of fact(4)

The output of the previous statement is 24 .
In Figure 13-1, the downward arrows represent the successive calls to the method fact ,and
the upward arrows represent the values returned to the caller, that is, the calling method.
While tracing the execution of the recursive method fact , note the following:
￿ Logically, you can think of a recursive method as having unlimited copies
of itself.
￿ Every call to a recursive method—that is, every recursive call—has its
own code and its own set of parameters and local variables.
￿ After completing a particular recursive call, control goes back to the
calling environment, which is the previous call. The current (recursive)
call must execute completely before control goes back to the previous
call. The execution in the previous call begins from the point immedi-
ately following the recursive call.

Direct and Indirect Recursion
A method is called directly recursive if it calls itself. A method that calls another method
and eventually results in the original method call is called indirectly recursive. For