Chapter 8

Recursive Thinking

We've seen amny times how one method can call another method. What we haven't seen is a method calling itself. Recursion is a programming technique in which a method calls itself. But before we get into the details of how we use recursion in a progrma, we need to explore the general idea of recursion. We have to be able to think recursively before we can use recursion as a programming technique.

In general, recursion means defining something in terms of itself. For example, consider the following definition of the word decoration:

decoration: any ornament or adornment used to decorate something

The word decorate is used to define the word decoration. Your English teacher may tell you not to use recursion when explaining the meaning of a word. However, in many situations, recursion is a good way to express an idea or definition. For example, suppose we wanted to formally define a list of one or more numbers, separated by commas. We could define the list recursively as being made up of either a number of a number followed by a comma followed by a list. This definition can be expressed as follows:

A List is a: number
	or a: number comma List

This recursive definition of List works for all of the following lists of numbers:

24,88,40,37
96,43
14,64,21,69,32,93,47,81,238,45,81,52,69
70

No matter how long a list is, the recursive definition describes it. A list with only one element, such as in the last example, 70, is defined completely by the first (nonrecursive)p art of the definition. FOr any list longer than one element, the recursive part of the definition (the part that refers to itself) is used over and over until the last element is reached. The last element in the list is always defined by the nonrecursive part of the definition, in this case "number" instead of "number comma List" Figure 8.1 shows one list of numbers matches to the recursive definition of List.


...

Infinite Recursion

Note that the definition of List contains one part that is recursive and one part that is not. The part of the defintion  that is not recursive is called the base case. If all the parts were recursive, the recursion would never end. For example, if the definition of List was simply "a number followed by a comma followed by a List," no list could ever end. This problem is called inifnite recursion. It is like an infinite loop except that hte "loop" occurs in the definition itself.

you should be careful to avoidn infinite recursion. Any recursive definition must have a base case that does not result in recursion. The base case of the List definition is a single number that is not followed by anything. In other words, when the last number in the list is reached, the base case option ends the recursion.

Recursion in Math

Let's look at an example of recursion in math. The value reffered to as N! (pronounced N factorial) is defined for any positive integer N as the product of all integers between 1 and N inclusive. THerefore, 3! is defined as:

3! = 3*2*1 = 6

and 5! is defined as: 5! = 5*4*3*2*1 = 120.


Mathematical formulas are often expressed recursively. The definition of N! can be expressed recursively as: 1! = 1; N! = N*(N-1)! for N>1

The base case of this definition is 1!, which is defined as 1. All other values of N! (for N>1) are defined recursively as N times the value of (N-1)!. In other words, the factorial function is defined in terms of the factorial functions: which is recursion!

By this definition, 50! is equal to 50*49!. And 49! is equal to 49*48!. And 48! is equal to 48*47!. This continues until we get to the base case of 1. Because N! is defined only for positive integers, this definition is complete and will always conclude with the base case.
The next section describes how recursion is used in programs.


Recursive Programming

Let's use some simple math to demonstrrate the concept of recursive programimng. Consider adding up the values between 1 and N inclusive, where N is any positive number. We can express this as N plus the sum of the values from 1 to N-1, as shown in Figure 8.2

For example, the sum of the values between 1 and 20 is equal to 20 plus the sum of the values between 1 and 19. Continuing this approach, the sum of the values between 1 and 19 is euqal to 19 plus the sum of the values between 1 and 18. This may sound like a strange way to think about the problem, but it is a straightforward example that can be used to demonstrate how recursion is programme.d

As we mentioned earlier, in Java, as in many other programming languages, a method can call itself. Each call to the method creates a new environment in which to work. That is, all loocal bvariables and parameters are newly defined with their own unique data space every tim ethe method is called. Each parameter is given an initial value bnased on the new call. Each time a method ends, processing returns to the method that called it ( which may be an earlier invocation of the same method). These rules are no different from those of "regular" method invocation.

A recursive solution to the summation problem is definbed by the following recursive method called sum:

public int sum (int sum) {
int result;
if(num == 1) { result = 1; }
else { result = num+sum(num-1); }
return result;
}

Note that this method is basically our recursive definition that the sum of the numbers between 1 and N is equal to N plus the sum of the numbers beteween 1 and N-1. The sum method is recursive because sum calls itself. The parameter passed to sum is reduced by one each time sum is called until it reaches the base case of 1. Recursive methods always have an if-else statement, with one of the branches, usually the first one, rpersenting the base case, as in this example.

Suppose the main method calls sum, passing it an intiail value of 1, which is stored in the parameter num. Since num is equal to 1, the result of 1 is returned to main and no recursion occurs.

Now let's trace the execution of the sum method when it is passed an initial value of 2. Since num does not equal 1, sum is called again with an argument of num-1, or 1. This is a new call to the method sum, with a new parameter num and a new local variable result. Since htis num is equal to 1 in this invocation, the result of 1 is returned without any more recursive calls. Control returns to the first version of sum that was invoked. The return value of 1 is added to the initial value of num in that call to sum, which is 2. therefore, result is assigned the value of 3, which is returned ot hte 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 more recursive calls are made. The recursion begins to fold back into the earlier versions of the sum method, returning the approprioate value each time. Each return value ocntributes to the computation of the sum at the next 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 runtime error indicating that memory has been used up.

Trace the sum function with different beginning values of num umntil this processing becomes familiar. Figure 8.1 illustrates the recursive calls when main invokes sum to determine the su m of the integers from 1 to 43. each box represents a copy of the method as it is invoked, allocating space to store the formal parameters and nay local variables. Invocations are shown as solid lines, and returns a dotted lines. The return value result is shown at each step. The recursive path is followed completely until the base case is reached; the calls then begin to return their result up through the chain.


Recursion versus iteration

of course, there is a nonrecursive solution to the summation problem we just explored. one way to add up the numbers between 1 and num inclusive is an iterative manner is as follows:
	sum = 0
	for (int number = 1; number <= num; number++) 
	sum+=number;
This solution is certainly more straightforward than the recursive version. We used the summation problem to demonstrate rrecursion because it is simple, not because you would normally use recursion to solve it. Recursion requires many method invocations so, in this case, it is more complicated solution than doing with iteration.

A programmer must learn when ot use recursion and when not to use it. Which approach is best dependents on the problem being solved. All probles can be solved in an iterative manner, but in some cases the iterative version is much more complicated. Recursion, for some problems, lets us create relatively short, legant programs.

Direct versus Indirect Recursion

Direct recursion is when a method invokes itself, such as when sum calls sum. Indirect recursion is when a method invokes another method, eventually resulting in the original method being invoked again. For example, if the method m1 invokes method m2, and m2 invokes method m1, we can say that m1 is indirectly recursive. The amount of indirection could be several levels deep, as when m1 invokes m2, which invokes m3, which invokes m4, which invokes m1. Figure 8.4 shows indirect recursion. The method invocation are the solid lines, anbd returns are the dotted lines. The entire onviocation pathj is followed, and then the recursion unravels following the return path.

Indirect recursion requires all of the same attention to base case s that direct recursion requires. Indirect recursion can be harder to trace betweecause of the method calls ion between. So we need to be extra careful when designing or evaluating indirectly recursive methods. Make sure that the indirection is turly necessary and clearly explain ed in documentation.

Using Recursion

Each of the following sections descrfibesa a particular recursive problem.  For each one, we look at exactly how recursion works and how a base case ends, thje recursion. As you examine these examples, think about how complicated a nonrecursive solution for each problem would be.

Solving A Mase

Solving a maze invovles a great deal of trial and error: you follow a path, backtrack when you cannot go farthter, and try other routes. Recursion can handle this nicely. The program shown in Listing 8.1 dcreates a Maze object and attempts to solve it.

The maze class shown in listing 8.2 uses a two-dimensional array of integers to represent the maze. The gaol is to move from the top left conrer (the entry point) to the bottom ....