Programming and Problem Solving with Java

13.1 W h a t I s Recursion? | 637

where nequals 1: x^1 is x. The case (or cases) for which an answer is explicitly
known is called the base case. The case for which the solution is expressed in
terms of a smaller version of itself is called the recursiveor general case.A recursive
algorithmexpresses the solution in terms of a call to itself, a recursive call. A re-
cursive algorithm must terminate; that is, it must have a base case.

Power Function Implementation

We use anifstatement to determine which case is being executed. The following
method implements the power function with the general case and the base case
marked in the comments.

public static intpower(int x, int n)
// Returns x raised to the power n
// Assumption: x is a valid integer and n is greater than 0
// Note: Large exponents may result in integer overflow
{
if (n == 1)
returnx; // Base case
else
returnx * power(x, n – 1); // Recursive call
}

We can think of each recursive call to poweras creating a com-
pletely new copy of the method, each having its own copies of the
parameters xand n. The value of xremains the same for each ver-
sion of power, but the value of ndecreases by 1 for each call until
it becomes 1.
Let’s trace the execution of this recursive method, with the fol-
lowing initial call:

xToN = power(2, 3);

We will use a new format to trace recursive routines: We num-
ber the calls and then discuss what is happening in paragraph
form. This trace is also summarized in Figure 13.1, where each
box represents a call to thepowermethod. The values for the pa-
rameters for that call are shown in each box. Refer to the figure
while you work through the trace in paragraph form.
Call 1:poweris called with the number equal to 2 and the ex-
ponent equal to 3. Within power, the parameters xand nare ini-
tialized to 2 and 3, respectively. Because nis not equal to 1,poweris called recursively with x
and n 1 as arguments. Execution of Call 1 pauses until an answer is sent back from this re-
cursive call.

Base case The case for which

the solution can be stated non-

recursively

General case The case for

which the solution is expressed

in terms of a smaller version of

itself; also known as the recursive

case

Recursive algorithm A solu-

tion that is expressed in terms of

(1) smaller instances of itself and

(2) a base case

power( 2 , 3 )

Call 1:

Call 2:

Call 3:

Returns 8.

Returns 4.

Returns 2.

xn

23

xn

22

xn

2 1

Figure 13.1 Execution of power( 2 , 3 )