Recursion - Java: How to Program Early Objects - page 778

Chapter Recursion examples and exercises in this topic

19 Merge Sort (Fig. 19.6)

Linear Search (Exercise 19.8)
Binary Search (Exercise 19.9)
Quicksort (Exercise 19.10)

21 Binary-Tree Insert (Fig. 21.17)

Preorder Traversal of a Binary Tree (Fig. 21.17)
Inorder Traversal of a Binary Tree (Fig. 21.17)
Postorder Traversal of a Binary Tree (Fig. 21.17)
Print a Linked List Backward (Exercise 21.20)
Search a Linked List (Exercise 21.21)

Fig. 18.1 | Summary of the recursion examples and exercises in this text. (Part 2 of 2.)

18.2 Recursion Concepts
Recursive problem-solving approaches have a number of elements in common. When a
recursive method is called to solve a problem, it actually is capable of solving only the sim-
plest case(s) , or base case(s) . If the method is called with a base case , it returns a result. If
the method is called with a more complex problem, it divides the problem into two con-
ceptual pieces—a piece that the method knows how to do and a piece that it does not
know how to do. To make recursion feasible, the latter piece must resemble the original
problem, but be a slightly simpler or smaller version of it. Because this new problem re-
sembles the original problem, the method calls a fresh copy of itself to work on the smaller
problem—this is referred to as a recursive call and is also called the recursion step . The
recursion step normally includes a return statement, because its result will be combined
with the portion of the problem the method knew how to solve to form a result that will
be passed back to the original caller. This concept of separating the problem into two
smaller portions is a form of the divide-and-conquer approach introduced in Chapter 6.
The recursion step executes while the original method call is still active (i.e., it has not
finished executing). It can result in many more recursive calls as the method divides each
new subproblem into two conceptual pieces. For the recursion to eventually terminate,
each time the method calls itself with a simpler version of the original problem, the
sequence of smaller and smaller problems must converge on a base case . When the method
recognizes the base case, it returns a result to the previous copy of the method. A sequence
of returns ensues until the original method call returns the final result to the caller. We'll
illustrate this process with a concrete example in Section 18.3.
A recursive method may call another method, which may in turn make a call back to
the recursive method. This is known as an indirect recursive call or indirect recursion . For
example, method A calls method B , which makes a call back to method A . This is still recur-
sion, because the second call to method A is made while the first call to method A is
active—that is, the first call to method A has not yet finished executing (because it's
waiting on method B to return a result to it) and has not returned to method A 's original
caller.