Unit 5 JAVA

algorithm

sequence of steps for solving a problem. Algorithms are like recipes.

recursive algorithm

algorithm that breaks the problem into smaller subproblems and applies the same algorithm to solve the smaller subproblems.

recursive algorithm example

Sorting envelopes by zipcode:

If N is 1, done.
Else, find the middle zipcode. Put all zipcodes less than the middle zipcode on the left, all greater ones on the right. Then sort the left, then sort the right.

recursive method.

A method that calls itself.

is there a difference in how we define the parameters of a recursive versus non-recursive method?

No

Recursive search (general)

Consider a guessing game program where a friend thinks of a number from 0 to 100 and you try to guess the number, with the friend telling you to guess higher or lower until you guess correctly.

binary search

algorithm begins at the midpoint of the range and halves the range after each guess.

Recursive search method

A recursive method is a natural match for the recursive binary search algorithm. Has an if-else statement. The if branch ends the recursion, known as the base case. The else branch has recursive calls. Such an if-else pattern is common in recursive methods.

recursive method example

A method guessNumber(lowVal, highVal, scnr) has parameters that indicate the low and high sides of the guessing range and a Scanner object for getting user input. The method guesses at the midpoint of the range. If the user says lower, the method calls guessNumber(lowVal, midVal, scnr). If the user says higher, the method calls guessNumber(midVal + 1, highVal, scnr).

base case

the if branch that ends the recursion

Recursively searching a sorted list

Search is commonly performed to quickly find an item in a sorted list stored in an array or ArrayList. Consider a list of attendees at a conference, whose names have been stored in alphabetical order in an array or ArrayList. The following quickly determines whether a particular person is in attendance.

example for recursively searching a sorted list

findMatch() restricts its search to elements within the range lowVal to highVal. main() initially passes a range of the entire list: 0 to (list size - 1). findMatch() compares to the middle element, returning that element's position if matching. If not matching, findMatch() checks if the window's size is just one element, returning -1 in that case to indicate the item was not found. If neither of those two base cases are satisfied, then findMatch() recursively searches either the lower or upper half of the range as appropriate.

Creating a recursive method

• Write the base case -- Every recursive method must have a case that returns a value without performing a recursive call. That case is called the base case. A programmer may write that part of the method first and then test. There may be multiple base cases.

• Write the recursive case -- The programmer then adds the recursive case to the method.

Common errors

A common error is to not cover all possible base cases in a recursive method. Another common error is to write a recursive method that doesn't always reach a base case. Both errors may lead to infinite recursion, causing the program to fail.

outer method

intended to be called from other parts of the program, like the method int calcFactorial(int inVal).

inner method

intended only to be called from that outer method, for example a method int calcFactorialHelper(int inVal).

inner and outer methods

The outer method may check for a valid input value, e.g., ensuring inVal is not negative, and then calling the inner method. Commonly, the inner method has parameters that are mainly of use as part of the recursion, and need not be part of the outer method, thus keeping the outer method more intuitive.

recursive methods can have multiple base cases?

True

Before writing a recursive method, a programmer should determine:

1. Does the problem naturally have a recursive solution?

2. Is a recursive solution better than a non-recursive solution?