Recursion - Multimedia Introduction to Programming Using Java - page 406

15.3 Execution of recursive calls

Understanding how a recursive method call is executed and understanding what
a recursive method call does are two different activities. Separate the two com-
pletely in your mind.
Understanding what a method call does requires looking at the specification
of the method. Make a copy of the specification and replace all occurrences of
the method parameters by the arguments of the call; the result is a command, usu-
ally in a mixture of English and math, that is equivalent to the method call. It
does not matter whether the method called is recursive or not; understanding
what it does is the same.
However, you may be wondering how recursion works. Suppose in the body
of a function factorial(n) there is a call factorial(n - 1) . Evaluating fac-
torial(n - 1) requires executing the method body; how can the method body
be executed a second time before its first execution is finished?
The answer to this is simple. If you evaluate an initial call factorial(3) ,
say, following precisely the steps presented in Sec. 2.7.2, you will see that those
steps work for recursive as well as non-recursive calls. Nothing new has to be
learned to handle recursion! Whenever a method is called, a new frame is creat-
ed and pushed on the call stack, and that frame is destroyed only when the call
completes. If there are 30 recursive, uncompleted calls to factorial , then the
call stack contains 30 frames for factorial .
Activity 15-2.1 shows evaluation of recursive calls, showing how the call
stack changes, in a way that we cannot match on paper. We urge you to watch it
now to gain full understanding. You will come to understand that the steps pre-
sented in Sec. 2.7.2 work for recursive as well as non-recursive calls.
The depth of recursion at any point of execution in a call of a recursive
method is the number of frames that are currently in use. Each of the frames takes
a certain amount of space, say f bytes of memory, and it also takes time to allo-
cate the space and to remove it. If the maximum depth of recursion during exe-
cution of a method call is m , then m*f bytes of memory are required during exe-
cution. For some applications, this space requirement may be a problem, and
people have been known to eschew recursion in favor of loops because of it.

Activity 15-2.1
shows execu-
tion of recursive
calls in a way
that we cannot
do here. Watch
that activity!

/** Sort b[h..k] */
public static void mergesort( int [] b, int h, int k) {
if (h >= k)
{ return ; }
int e= (h + k) / 2;
mergesort(b, h, e); // Sort b[h..e]
mergesort(b, e + 1, k); // Sort b[e+1..k]
merge(b, h, e, k); // Merge the two sorted segments

}
Figure 15.7: Function mergesort