Recursion - Java Software Solutions: Foundations of Program Design - page 588

of sum that was invoked. The return value of 1 is added to the ini-
tial value of num in that call to sum , which is 2. Therefore, result
is assigned the value 3, which is returned to the main method. The
method called from main correctly calculates the sum of the integers
from 1 to 2 and returns the result of 3.
The base case in the summation example is when N equals 1, at which point
no further recursive calls are made. The recursion begins to fold back into the
earlier versions of the sum method, returning the appropriate value each time.
Each return value contributes to the computation of the sum at the higher level.
Without the base case, infinite recursion would result. Each call to a method
requires additional memory space; therefore infinite recursion often results in a
run-time error indicating that memory has been exhausted.
Trace the sum function with different initial values of num until this processing
becomes familiar. Figure 12.3 illustrates the recursive calls when main invokes
sum to determine the sum of the integers from 1 to 4. Each box represents a copy
of the method as it is invoked, indicating the allocation of space to store the
formal parameters and any local variables. Invocations are shown as solid lines,

KEY CONCEPT
A careful trace of recursive process-
ing can provide insight into the way
it is used to solve a problem.

main

result =10

sum(4)

sum

result =6

sum(3)

sum

result =3

sum(2)

sum

result =1

sum(1)

sum

FIGURE 12.3 Recursive calls to the sum method