Java Unit 1
Recursion
1.1 Description of Recursion
1.2 Implementation and Execution of Recursive Code
1.3 Details of Recursion
1.4 Recursion and Looping, Recursion with Two Parameters
1.1 Description of Recursion
When a method contains a call to itself, this is referred to as recursion. Consider the following class containing the skeleton of a static method:
public class MyClass
{
public static int mymethod(int parameterone)
{
int parametertwo;
…
return mymethod(parametertwo);
}
}
Java supports recursion, and this skeleton illustrates the syntax for recursion. mymethod() contains a call to itself. Notice that syntactically, it’s not necessary to write the call as MyClass.mymethod(…) because the call occurs within code belonging to MyClass.
The picture shown below represents a rack of pool balls. It will be used to illustrate how a recursive definition can be developed for the summation of positive integers.
J
J J
J J J
J J J J
J J J J J
You can ask the following question as you move from the top row down: How does the total number of balls in the rack depend on the number of rows? For a rack containing 5 rows, it’s easy enough to figure this out and put the information in a little table:
# of rows sum of balls in rows total number of balls in rack
1 1 1
2 1 + 2 3
3 1 + 2 + 3 6
4 1 + 2 + 3 + 4 10
5 1 + 2 + 3 + 4 + 5 15
Using mathematical notation these sums can be shown as a function:
Here is a different definition for the same function. It is recursive:
Recursive case: n > 1
f(n) = n + f(n – 1)
Base case: n = 1
f(1) = 1
The idea is that for any integer n greater than 1, the function can be defined in terms of n and the function applied to n – 1. For n = 1, the value of the function is simply defined to be 1. This is the base case, where the value of the function is no longer defined in terms of itself.
Here is a definition of another mathematical function. For x real and n some non-negative integer, x raised to the nth power is the product of n factors x:
xn = x * x * … * x
If you look in a math book, you may find the following recursive definition for this:
Recursive case: n > 0
f(n) = x * f(n – 1)
= x * xn-1
Base case: n = 0
f(0) = x0 = 1
Lots of examples are possible. In each you would observe that the definition of the function consists of two parts. In the first, recursive part of the definition, the function is defined in terms of itself. In the second part of the definition, the base case, the function is concretely defined for some fixed value. In this second example the base case is defined for n = 0 rather than n = 1.
In the examples above, n was a positive integer. In the recursive part of the definition, f(n) was defined in terms of n and the f(n – 1). In other words, f(n) was defined in terms of an application of the function to a value 1 less. The base case defined f(n) for n = 0 or n = 1. These examples illustrate the general structure of recursion. n is decreased by 1 in each successive application of the recursive function. It is critical that n reach the value of the base case so that the recursion will stop.
1.2 Implementation and Execution of Recursive Code
A recursive definition can be implemented in code in order to calculate the value of a function. That part of the definition where the function is defined in terms of itself is implemented as a method that calls itself. The base case is also a necessary part of the implementation. Both parts will be illustrated in the examples that follow.
Shown below is a complete test program and class containing a static method with recursion that finds the number of balls in a pool rack. All elements of a correct implementation are present in the example. There is a certain redundancy in the use of the variable returnvalue and the return statements in the method. The example is written in this way in order to make it easier to pinpoint certain actions in the code in the explanations that follow. In the definitions above the recursive case was shown first. This emphasized the recursion. In this implementation and those that follow, the if statement tests for the base case, and it is handled first.
public class TestPool
{
public static void main(String[] args)
{
MyTerminalIO myterminal = new MyTerminalIO();
int myrows, myresult;
myterminal.print("How many rows of balls? ");
myrows = myterminal.getInt();
myresult = PoolClass.poolrack(myrows);
myterminal.println("This is the total number of balls: " + myresult);
}
}
public class PoolClass
{
public static int poolrack(int numofrows)
{
int returnvalue;
if(numofrows == 1)
{
returnvalue = 1;
return returnvalue;
}
else
{
returnvalue = numofrows + poolrack(numofrows – 1);
return returnvalue;
}
}
}
Note that the body of the method is structured as an if statement. If the base case has been reached, then a simple value can be returned. If the base case has not been reached, then another call to the method is made. In the call, the value of the parameter is decreased by 1. Successive calls approach and ultimately reach the value given in the base case, so the recursion will stop successfully.
It may not be clear just from looking at the code how recursion works. There is a general technique for understanding code which can be applied to this example. The technique involves tracing the parameter values and return values through a sequence of recursive calls. It is possible to draw a diagram using boxes to represent the calling program and the separate executions of the recursive method. When writing and debugging code, this can be done by hand, noting parameter values and return values in the diagram.
Here is such a diagram for the pool rack method where the calling program sends in an initial parameter value of 3. This diagram was produced by an applet which was designed to animate recursion. The path of execution goes down the left hand side through the sequence of activations of the recursive method, and back up the right hand side as each activation is done and returns a value.
The exact relationship between the different calls may still not be clear. In effect, recursive calls are stacked calls. Each activation of the method runs until it makes a recursive call. It then waits for that call to return a value before continuing to completion. In the diagram, main() and two activations of the method are stacked up waiting for the third activation of the method to complete. The third reaches the base case, completes, and returns to the second, which can then complete. When the second completes, it returns to the first, which completes and returns to main().
It is true that in a given class there is only one copy of a method’s code which is shared by any calls to it. Objects don’t get their own copies of methods. However, each call to a method is unique and can be identified. Any activation of the method also has its own copies of the values for any variables. Although only the variables are copied, for the purposes of explanation it is useful to illustrate the calling process as if there were multiple copies of the code, one calling the other. Such an illustration follows. Here is the call to the method in the main() method with a parameter value of 3:
int myresult = PoolClass.poolrack(3);
Here is the beginning of the first activation of the method. The value of the parameter coming in is 3. The method runs to the line shown in bold face. However, this line does not complete. The call to poolrack() is made, but the addition and the assignment of the result of the arithmetic cannot be done until a return value is received from the call. The first activation at this point simply waits.
public static int poolrack(int numofrows)
{
int returnvalue;
if(numofrows == 1)
{
returnvalue = 1;
return returnvalue;
}
else
{
returnvalue = numofrows + poolrack(numofrows – 1);
Here is the beginning of the second activation of the method. The value of the parameter coming in is 2. The method runs to the line shown in bold face. However, this line does not complete. The call to poolrack() is made, but the addition and the assignment of the result of the arithmetic cannot be done until a return value is received from the call. The second activation at this point simply waits.
public static int poolrack(int numofrows)
{
int returnvalue;
if(numofrows == 1)
{
returnvalue = 1;
return returnvalue;
}
else
{
returnvalue = numofrows + poolrack(numofrows – 1);
Here is the third activation of the method. The value of the parameter coming in is 1. The method runs to the line shown in bold face. This is the base case and at this point the third activation of the method completes. The value 1 is returned to the second activation of the method.
public static int poolrack(int numofrows)
{
int returnvalue;
if(numofrows == 1)
{
returnvalue = 1;
return returnvalue;
The second activation of the method now resumes execution. The value 1 is returned to it by the call to poolrack(). This is added to the variable numofrows, which has the value 2, and assigned to the variable returnvalue. This activation of the method runs to completion with the execution of the return statement, shown in bold face, which returns the value 3 to the first activation of the method.
returnvalue = numofrows + poolrack(numofrows – 1);
return returnvalue;
The first activation of the method now resumes execution. The value 3 is returned to it by the call to poolrack(). This is added to the variable numofrows, which has the value 3, and assigned to the variable returnvalue. This activation of the method runs to completion with the execution of the return statement, shown in bold face, which returns the value 6 to the calling program.
returnvalue = numofrows + poolrack(numofrows – 1);
return returnvalue;
This return statement returns the value 6 to the main() method. All activations of poolrack() have run to completion and the calling program can finish the execution of the calling statement shown below. The return value is assigned to the variable myresult and the calling program can continue execution.
int myresult = PoolClass.poolrack(3);
The pattern shown above with code fragments can be summarized in the following outline:
Call in main program
First activation of method, execution till recursive call
Second activation of method, execution till recursive call
Third activation of method, base case returns a value
Second activation resumes, runs to completion returning a value
First activation resumes, runs to completion returning a value
Calling program resumes execution
1.3 Details of Recursion
Some problems which can be solved using recursion are rather complex. We are only addressing relatively straightforward examples here. You might observe that the algorithm for finding the number of balls in a pool rack could be implemented using a loop rather than recursion. The fragment below illustrates how simple this can be:
int sum = 0;
for(int i = 1; i < n; i++)
sum = sum + i;
This is simpler than recursion, and in general, any of the examples given here using recursion could be implemented using loops. However, you need to know about recursion for at least two reasons: 1) Because it is syntactically possible to call a method within itself, even if you never intend to do so, you need to know what happens in case you do so accidentally. In other words, the existence of this capability in the syntax leads to the possibility of new logic errors which you need to be aware of. 2) Some more advanced concepts in computer science are more simply explained in terms of recursion rather than loops. For this reason you should have some idea of this abstraction even if you never plan on using it in your own programs.
Once you learned how to program using loops, you found out there was a special kind of problem that they were prone to: an infinite loop. Likewise, once you learn how to program using recursion, you have the possibility of a new kind of error: infinite recursion. This kind of error is particularly nasty. Usually it is possible to break an infinite loop by closing the program window or using CTRL+ALT+DEL. However, infinite recursion can cause the process or system to lock up, making it necessary to restart in order to continue.
Why does this happen? The answer is that each call to a method takes a certain amount of space in system memory to hold copies of the parameters, local variables, and other things that belong to the call. When infinite recursion happens, all free memory can eventually be taken up by the calls, until no memory is left. When the process or system no longer has any free memory to work with, it locks up. It may be possible to deal with the offending process by entering the CTRL+ALT+DEL command. Depending on the configuration of the system, this may not work, and it would be necessary to completely restart the system in order to recover from infinite recursion. Debugging recursion requires careful reading of the code because the compiler may not detect problems and run time problems can be so intractable.
There are many ways to make mistakes and many unusual results that might come from incorrect recursive code, but the most important and typical kinds of mistake have to do with the base case. Either the body of the method is not structured as an if with two alternatives, one of them the base case; or the test condition of the base case is not correctly written; or the sequence of values sent in successive calls to the method do not approach and ultimately reach the value tested in the base case condition. These defects can lead to infinite recursion and other problems.
1.4 Recursion and Looping, Recursion with Two Parameters
The pool rack example could be implemented using a for loop. It is also possible to write recursive methods that accomplish things that you might do with a while loop. In the unit on looping, division was implemented as repeated subtraction. Dividing by a specific divisor is a useful starting point for illustrating how to define such a function recursively. Here is a definition for finding how many times the constant value 2 will go evenly into another number. The value 1 which is added in the recursive case counts how many times recursion occurs. This count gives the result of the division. Notice that in the recursive case n is no longer decremented by 1. It is decremented by 2. The test for the base case is an inequality rather than an equality since the values that n takes on vary depending on whether it is initially odd or even.
Recursive case: n >= 2
f(n) = 1 + f(n – 2)
Base case: n < 2
f(n) = 0
Here is a sample implementation. The recursive method recursiveDivisionByTwo() is typed int and takes an int parameter named dividend.
public static int recursiveDivisionByTwo(int dividend)
{
if(dividend < 2)
return 0;
else
return 1 + recursiveDivisionByTwo(dividend – 2);
}
Building on the foregoing, it is possible to write a recursive definition for the general division function. The function has two parameters. Adding 1 in the recursive case again counts how many times the recursion occurs. In this definition the first parameter for the recursive case is dividend – divisor. The amount decremented each time is always the same, but divisor can be any (positive integer) value. The second parameter is the divisor, which is passed down unchanged through all of the calls.
Recursive case: dividend >= divisor
f(dividend, divisor) = 1 + f(dividend – divisor, divisor)
Base case: dividend < divisor
f(dividend, divisor) = 0
Here is a complete driver program and an implementation of this function. As usual, this is not a general implementation, but it works for appropriate input values and illustrates the key points. Notice that a variable retval is used in the implementation.
public class GenRecDivProg
{
public static void main(String[] args)
{
MyTerminalIO myterminal = new MyTerminalIO();
int retval;
int dividen, divisor;
myterminal.print("Enter the dividend: ");
dividend = myterminal.getInt();
myterminal.print("Enter the divisor: ");
divisor = myterminal.getInt();
retval = GenRecDivClass.genRecDiv(dividend, divisor);
myterminal.println(retval);
}
}
public class GenRecDivClass
{
public static int genRecDiv(int dividend, int divisor)
{
int retval = 0;
if(dividend < divisor)
return retval;
else
{
retval = 1 + genRecDiv(dividend - divisor, divisor);
return retval;
}
}
}
Just as division can be defined by repeated subtraction, finding a logarithm can be defined by repeated division. For a given number to find the log of, which will be represented by the variable name tofindlogof, and a given base, a simple recursive definition of the logarithm function would look like this:
Recursive case: tofindlogof >= base
f(tofindlogof, base) = 1 + f(tofindlogof / base, base)
Base case: tofindlogof < base
f(tofindlogof, base) = 0
The following example contains two static methods, both of which find a simple logarithm by doing repeated division. One does so with looping and the other with recursion. For positive input consisting of a given double tofindlogof and a given integer base, the code gives as output the largest integer value less than or equal to the logarithm for that number and base.
public class TestRecAndLoop
{
public static void main(String[] args)
{
MyTerminalIO myterminal = new MyTerminalIO();
double tofindlogof;
int base;
double answer;
myterminal.println("What number would you like to find the log of?");
tofindlogof = myterminal.getDouble();
myterminal.println("What should the base of the logarithm be?");
base = myterminal.getInt();
answer = RecursionAndLooping.myLogLooping(tofindlogof, base);
myterminal.println("The looping answer is: " + answer);
answer = RecursionAndLooping.myLogRec(tofindlogof, base);
myterminal.println("The recursive answer is: " + answer);
}
}
public class RecursionAndLooping
{
public static int myLogLooping(double tofindlogof, int base)
{
int retval = 0;
while(tofindlogof >= base)
{
tofindlogof = tofindlogof / base;
retval++;
}
return retval;
}
public static int myLogRec(double tofindlogof, int base)
{
int retval = 0;
if(tofindlogof < base)
return retval;
else
{
tofindlogof = tofindlogof / base;
retval = 1 + myLogRec(tofindlogof, base);
return retval;
}
}
Note that the following version of the recursive method would be more economical and compact, but it would also be more cryptic.
public static int myLogRec(double tofindlogof, int base)
{
int retval = 0;
if(tofindlogof > base)
{
tofindlogof = tofindlogof / base;
retval = 1 + myLogRec(tofindlogof, base);
}
return retval;
}
}
Отредактировано TaronTo (20-12-2009 21:09:48)
