Java Reference
In-Depth Information
returns 2
return f(1)*2
return f(1) = 1
n = 2
return f(0) * 1 = 1
n = 1
return f(0)=1
n = 2
FIGURE 14.5: Example of computing 2! recursively.
the variable n and the program jumps to the new return address. Now the return value will
be 2
1 = 2. Therefore, the method will return the value 2.
Note that, of course, we can write an iterative method to compute n !.
public static int f( int n) {
int result = 1;
while ( true ) {
if (n == 0) {
return result ;
result = result
n −− ;
The reason this non-recursive rewrite is possible and so simple is because there is a
single recursive call at the end of the original method. In literature, this case is sometimes
referred to as tail recursion . It can be shown that if a method contains a single recursive call
at the end of every execution branch, then we can easily rewrite our code and substitute
the recursive call with an infinite while loop. However, if there is a recursive call that is
not at the end of an execution branch, then this approach cannot be directly applied.
Our example of computing n ! recursively showed us that there is extra overhead
that is needed in order to make a recursive program work. Therefore, when possible,
one should try to develop non-recursive solutions. However, in some cases, a recursive
solution is the only option that is available short of implementing our own stack and
recursive calls.
Search WWH ::

Custom Search