Transcript Chapter 9 Slides

Chapter 9
Recursion
© 2006 Pearson Education Inc., Upper Saddle River, NJ. All rights reserved.
Overview
●
9.1
–
●
9.2
–
●
Recursive algorithms requires new techniques.
9.3 and 9.4
–
●
Introduce the recursive way of thinking.
Recursive sorting algorithms are introduced.
9.5
–
Converting recursive algorithms into a nonrecursive
form.
Computing Factorial
0! = factorial(0) = 1; // factorial is a method
n! = factorial(n) = n*factorial(n-1);
3! = 3 * 2 *1 = 6
factorial(3) = 3 * factorial(2)
= 3 * (2 * factorial(1))
= 3 * ( 2 * (1 * factorial(0)))
= 3 * ( 2 * ( 1 * 1)))
= 3 * ( 2 * 1)
=3*2
=6
Computing Factorial (recursive)
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
import javax.swing.JOptionPane;
public class ComputeFactorial {
/** Main method */
public static void main(String[] args) {
// Prompt the user to enter an integer
String intString = JOptionPane.showInputDialog(
"Please enter a non-negative integer:");
// Convert string into integer
int n = Integer.parseInt(intString);
// Display factorial
JOptionPane.showMessageDialog(null,
"Factorial of " + n + " is " + factorial(n));
}
Computing Factorial (recursive)
1.
/** Return the factorial for a specified index */
static long factorial(int n) {
2.
if (n == 0) // Stopping condition
3.
return 1; // factorial(0) = 1
4.
else
5.
// factorial(n) = n*factorial(n-1);
return n * factorial(n - 1);
6.
}
7.
8.
// Call factorial recursively
}
animation
Computing Factorial
factorial(0) = 1;
factorial(n) = n*factorial(n-1);
factorial(3)
animation
Computing Factorial
factorial(0) = 1;
factorial(n) = n*factorial(n-1);
factorial(3) = 3 * factorial(2)
animation
Computing Factorial
factorial(0) = 1;
factorial(n) = n*factorial(n-1);
factorial(3) = 3 * factorial(2)
= 3 * (2 * factorial(1))
animation
Computing Factorial
factorial(0) = 1;
factorial(n) = n*factorial(n-1);
factorial(3) = 3 * factorial(2)
= 3 * (2 * factorial(1))
= 3 * ( 2 * (1 * factorial(0)))
animation
Computing Factorial
factorial(0) = 1;
factorial(3) = 3 * factorial(2)
factorial(n) = n*factorial(n-1);
= 3 * (2 * factorial(1))
= 3 * ( 2 * (1 * factorial(0)))
= 3 * ( 2 * ( 1 * 1)))
animation
Computing Factorial
factorial(0) = 1;
factorial(n) = n*factorial(n-1);
factorial(3) = 3 * factorial(2)
= 3 * (2 * factorial(1))
= 3 * ( 2 * (1 * factorial(0)))
= 3 * ( 2 * ( 1 * 1)))
= 3 * ( 2 * 1)
animation
Computing Factorial
factorial(0) = 1;
factorial(n) = n*factorial(n-1);
factorial(3) = 3 * factorial(2)
= 3 * (2 * factorial(1))
= 3 * ( 2 * (1 * factorial(0)))
= 3 * ( 2 * ( 1 * 1)))
= 3 * ( 2 * 1)
=3*2
animation
Computing Factorial
factorial(0) = 1;
factorial(n) = n*factorial(n-1);
factorial(3) = 3 * factorial(2)
= 3 * (2 * factorial(1))
= 3 * ( 2 * (1 * factorial(0)))
= 3 * ( 2 * ( 1 * 1)))
= 3 * ( 2 * 1)
=3*2
=6
animation
Trace Recursive factorial
Executes factorial(4)
factorial(4)
Step 0: executes factorial(4)
Step 9: return 24
return 4 * factorial(3)
Step 1: executes factorial(3)
Step 8: return 6
return 3 * factorial(2)
Step 2: executes factorial(2)
Step 7: return 2
Stack
return 2 * factorial(1)
Step 6: return 1
Step 3: executes factorial(1)
return 1 * factorial(0)
Step 4: executes factorial(0)
Step 5: return 1
return 1
Main method
animation
Trace Recursive factorial
factorial(4)
Step 0: executes factorial(4)
Step 9: return 24
Executes factorial(3)
return 4 * factorial(3)
Step 1: executes factorial(3)
Step 8: return 6
return 3 * factorial(2)
Step 2: executes factorial(2)
Step 7: return 2
Stack
return 2 * factorial(1)
Step 6: return 1
Step 3: executes factorial(1)
return 1 * factorial(0)
Step 4: executes factorial(0)
Step 5: return 1
return 1
Space Required
for factorial(4)
Main method
animation
Trace Recursive factorial
factorial(4)
Executes factorial(2)
Step 0: executes factorial(4)
Step 9: return 24
return 4 * factorial(3)
Step 1: executes factorial(3)
Step 8: return 6
return 3 * factorial(2)
Step 2: executes factorial(2)
Step 7: return 2
Stack
return 2 * factorial(1)
Step 6: return 1
Step 3: executes factorial(1)
return 1 * factorial(0)
Step 4: executes factorial(0)
Step 5: return 1
return 1
Space Required
for factorial(3)
Space Required
for factorial(4)
Main method
animation
Trace Recursive factorial
factorial(4)
Executes factorial(1)
Step 0: executes factorial(4)
Step 9: return 24
return 4 * factorial(3)
Step 1: executes factorial(3)
Step 8: return 6
return 3 * factorial(2)
Step 2: executes factorial(2)
Step 7: return 2
Stack
return 2 * factorial(1)
Step 6: return 1
Step 3: executes factorial(1)
return 1 * factorial(0)
Step 4: executes factorial(0)
Step 5: return 1
return 1
Space Required
for factorial(2)
Space Required
for factorial(3)
Space Required
for factorial(4)
Main method
animation
Trace Recursive factorial
factorial(4)
Executes factorial(0)
Step 0: executes factorial(4)
Step 9: return 24
return 4 * factorial(3)
Step 1: executes factorial(3)
Step 8: return 6
return 3 * factorial(2)
Step 2: executes factorial(2)
Step 7: return 2
Stack
return 2 * factorial(1)
Step 6: return 1
Step 3: executes factorial(1)
return 1 * factorial(0)
Step 4: executes factorial(0)
Step 5: return 1
return 1
Space Required
for factorial(1)
Space Required
for factorial(2)
Space Required
for factorial(3)
Space Required
for factorial(4)
Main method
animation
Trace Recursive factorial
factorial(4)
returns 1
Step 0: executes factorial(4)
Step 9: return 24
return 4 * factorial(3)
Step 1: executes factorial(3)
Step 8: return 6
return 3 * factorial(2)
Step 2: executes factorial(2)
Step 7: return 2
Stack
return 2 * factorial(1)
Step 6: return 1
Step 3: executes factorial(1)
return 1 * factorial(0)
Step 4: executes factorial(0)
Step 5: return 1
return 1
Space Required
for factorial(0)
Space Required
for factorial(1)
Space Required
for factorial(2)
Space Required
for factorial(3)
Space Required
for factorial(4)
Main method
animation
Trace Recursive factorial
factorial(4)
returns factorial(0)
Step 0: executes factorial(4)
Step 9: return 24
return 4 * factorial(3)
Step 1: executes factorial(3)
Step 8: return 6
return 3 * factorial(2)
Step 2: executes factorial(2)
Step 7: return 2
Stack
return 2 * factorial(1)
Step 6: return 1
Step 3: executes factorial(1)
return 1 * factorial(0)
Step 4: executes factorial(0)
Step 5: return 1
return 1
Space Required
for factorial(1)
Space Required
for factorial(2)
Space Required
for factorial(3)
Space Required
for factorial(4)
Main method
animation
Trace Recursive factorial
factorial(4)
returns factorial(1)
Step 0: executes factorial(4)
Step 9: return 24
return 4 * factorial(3)
Step 1: executes factorial(3)
Step 8: return 6
return 3 * factorial(2)
Step 2: executes factorial(2)
Step 7: return 2
Stack
return 2 * factorial(1)
Step 6: return 1
Step 3: executes factorial(1)
return 1 * factorial(0)
Step 4: executes factorial(0)
Step 5: return 1
return 1
Space Required
for factorial(2)
Space Required
for factorial(3)
Space Required
for factorial(4)
Main method
animation
Trace Recursive factorial
factorial(4)
returns factorial(2)
Step 0: executes factorial(4)
Step 9: return 24
return 4 * factorial(3)
Step 1: executes factorial(3)
Step 8: return 6
return 3 * factorial(2)
Step 2: executes factorial(2)
Step 7: return 2
Stack
return 2 * factorial(1)
Step 6: return 1
Step 3: executes factorial(1)
return 1 * factorial(0)
Step 4: executes factorial(0)
Step 5: return 1
return 1
Space Required
for factorial(3)
Space Required
for factorial(4)
Main method
animation
Trace Recursive factorial
factorial(4)
returns factorial(3)
Step 0: executes factorial(4)
Step 9: return 24
return 4 * factorial(3)
Step 1: executes factorial(3)
Step 8: return 6
return 3 * factorial(2)
Step 2: executes factorial(2)
Step 7: return 2
Stack
return 2 * factorial(1)
Step 6: return 1
Step 3: executes factorial(1)
return 1 * factorial(0)
Step 4: executes factorial(0)
Step 5: return 1
return 1
Space Required
for factorial(4)
Main method
animation
Trace Recursive factorial
returns factorial(4)
factorial(4)
Step 0: executes factorial(4)
Step 9: return 24
return 4 * factorial(3)
Step 1: executes factorial(3)
Step 8: return 6
return 3 * factorial(2)
Step 2: executes factorial(2)
Step 7: return 2
Stack
return 2 * factorial(1)
Step 6: return 1
Step 3: executes factorial(1)
return 1 * factorial(0)
Step 4: executes factorial(0)
Step 5: return 1
return 1
Main method
factorial(4) Stack Trace
Required
5 Space
for factorial(0)
Required
1 Space
for factorial(4)
Required
4 Space
for factorial(1)
Space Required
for factorial(1)
Required
3 Space
for factorial(2)
Space Required
for factorial(2)
Space Required
for factorial(2)
Required
2 Space
for factorial(3)
Space Required
for factorial(3)
Space Required
for factorial(3)
Space Required
for factorial(3)
Space Required
for factorial(4)
Space Required
for factorial(4)
Space Required
for factorial(4)
Space Required
for factorial(4)
Required
6 Space
for factorial(1)
Space Required
for factorial(2)
Required
7 Space
for factorial(2)
Space Required
for factorial(3)
Space Required
for factorial(3)
Required
8 Space
for factorial(3)
Space Required
for factorial(4)
Space Required
for factorial(4)
Space Required
for factorial(4)
Required
9 Space
for factorial(4)
Other Examples
f(0) = 0;
f(n) = n + f(n-1);
Example: compute f(5) ?
Fibonacci Numbers
Finonacci series: 0 1 1 2 3 5 8 13 21 34 55 89…
indices: 0 1 2 3 4 5 6 7
8
9
10 11
fib(0) = 0;
fib(1) = 1;
fib(index) = fib(index - 2) + fib(index - 1);
for index >=2
fib(3) = fib(1) + fib(2)
= fib(1) + (fib(0) + fib(1))
=1+0+1=2
ComputeFibonacci
Run
Fibonnaci Numbers, cont.
fib(4)
17: return fib(4)
0: call fib(4)
return fib(3) + fib(2)
11: call fib(2)
10: return fib(3)
1: call fib(3)
16: return fib(2)
return fib(2) + fib(1)
7: return fib(2)
2: call fib(2)
9: return fib(1)
return fib(1) + fib(0)
5: call fib(0)
4: return fib(1)
3: call fib(1)
return 1
6: return fib(0)
return 0
return fib(1) + fib(0)
8: call fib(1)
return 1
13: return fib(1)
return 1
14: return fib(0)
12: call fib(1)
15: return fib(0)
return 0
Characteristics of Recursion
●
All recursive methods have the following characteristics:
–
One or more base cases (the simplest case) are used to stop
recursion.
–
Every recursive call reduces the original problem, bringing it
closer to a base case until it becomes that case.
In general, to solve a problem using recursion, you break
it into subproblems.
●
If a subproblem resembles the original problem, you can
apply the same approach to solve the subproblem
recursively.
●
This subproblem is almost the same as the original
problem in nature with a smaller size.
●
Thinking Recursively
Thinking Recursively
Thinking Recursively
One-disk puzzle is trivial.
●
●
The puzzle for two disks
Thinking Recursively
●
●
●
●
Method for the three-disk puzzle
Lines 4 to 6: move the first 2 disks from the source to the spare peg (use the
source peg as “source”, dest peg as “spare”, and the spare peg as “dest”).
Line 8: move the last (bottom) peg from source to dest.
Lines 10 to 12: move the first 2 disks from the spare peg to the dest peg (use
the spare peg as “source”, source peg as “spare” and the dest peg as “dest”).
Thinking Recursively
●
●
Rewrite hanio2() using hanoi1()
By invoking hanoi2() we can write a shorter
version of hanoi3().
Thinking Recursively
●
We now have a pattern that will allow us to write
a method to solve the puzzle for any number of
disks.
–
●
It would be much better if we could write a single
method which would work for any number of disks.
Recursive method
–
A method which invokes itself.
Thinking Recursively
●
Base case
–
To prevent the recursion from continuing indefinitely
–
It is the stop condition.
Thinking Recursively
●
In general, to solve a problem recursively, we
have two cases:
–
The base case, where we can solve the problem
directly.
–
The recursive case, where we solved the problem
in terms of easier subproblems.
●
Subproblem leads to the base case.
Tower of Hanoi (recursive)
1.
import javax.swing.JOptionPane;
2.
public class TowersOfHanoi {
3.
/** Main method */
4.
public static void main(String[] args) {
5.
// Read number of disks, n
6.
String intString = JOptionPane.showInputDialog(null,
7.
"Enter number of disks:");
8.
// Convert string into integer
9.
int n = Integer.parseInt(intString);
10.
// Find the solution recursively
11.
System.out.println("The moves are:");
12.
moveDisks(n, 'A', 'B', 'C');
13.
}
Tower of Hanoi (recursive), cont.
1.
/** The method for finding the solution to move n disks
from fromTower to toTower with auxTower */
2.
public static void moveDisks(int n, char fromTower,
3.
4.
char toTower, char auxTower) {
5.
if (n == 1) // Stopping condition
System.out.println("Move disk " + n + " from " +
6.
fromTower + " to " + toTower);
7.
else {
8.
9.
moveDisks(n - 1, fromTower, auxTower, toTower);
10.
System.out.println("Move disk " + n + " from " +
fromTower + " to " + toTower);
11.
moveDisks(n - 1, auxTower, toTower, fromTower);
12.
}
13.
}
14.
15.
}
Thinking Recursively
●
Printing a LinkedList backward. (a, b, c  c, b, a)
–
●
Iterative approach (Figure 9-11, p228)
This method works, but it is not very efficient.
–
–
Invokes the get() method each time.
Its time complexity is Θ(n2).
Thinking Recursively
●
Recursive solution for printing a LinkedList backward:
–
If there are no nodes, return the empty String. (base case)
–
Otherwise, generate a String for the rest of the list (the part after the
first item). Add the first item to the end of this String and return it.
Thinking Recursively
●
●
To show that a recursive algorithm works
correctly:
–
Show that the base case works correctly.
–
Show that if the recursive method works for
a problem of size n – 1, then it works for a
problem of size n.
Base case
–
ToStringReversed() returns “()”.
Thinking Recursively
●
Assume that node is a reference to the first
of a chain of n nodes
Thinking Recursively
●
●
●
If we assume that the recursive invocation
toStringReversedHelper(node.getNext())
correctly returns the String "D C B“
then toStringReversedHelper(node.getNext())
+ Node.getItem() + " " evaluates to "D C B A
", which is what we want.
If it works for n-1 nodes, it works for a chain of
n nodes.
Thinking Recursively
●
ToStringReversed() for our ArrayList class.
–
Again we need a helper method, and the design
of the algorithm is similar:
●
●
If there are no elements being considered, return the
empty String.
Otherwise, generate a String for all of the elements
after the current one. Add the current element to the
end of this String and return it.
Thinking Recursively
Fig. 9-14: The toStringReversed method for ArrayList class
Analyzing Recursive Algorithms
●
Analyze a recursive algorithm we must think
recursively, in terms of a base case and a recursive
case.
–
●
toStringReversedHleper() — a recurrence.
Solving a recurrence means transforming it with T(n)
on the left and no mention of T (make T disappear) on
the right.
Analyzing Recursive Algorithms
●
The base must work exactly to constitute a
solution.
–
Guessing T(n) = n + 1
–
ToStringReversed() runs in linear time.
–
Its time complexity is Θ(n).
–
It is much better than the iterative approach Θ(n2) .
Analyzing Recursive Algorithms
●
The recurrence for hanoi():
Analyzing Recursive Algorithms
●
●
●
This expansion continues until we have many copies
of T(1).
There are n levels, corresponding to T(n) down
through T(1).
Therefore the bottommost level is level n-1.
Analyzing Recursive Algorithms
●
Total number of steps: (p234)
●
Verification that the solution is correct.
●
Solved! We conclude that hanoi() takes time in Θ(2n).
Analyzing Recursive Algorithms
●
The recursion tree method can be used to analyze
algorithms with only one recursive call.
–
Example:
Assuming n is even:
Merge Sort
●
The recursive idea behind merge sort is:
–
–
–
–
If there is only one number to sort, do nothing.
Otherwise, divide the numbers into two
groups.
After divided, if data size is odd, then the left
group will be one larger than the second
group. For example, if there are 9 integers to
be sorted, then the left group will have 5
numbers and the right group will have 4
numbers after divided.
Recursively sort each group, then merge the
two sorted groups into a single sorted array.
Merge Sort
Merge Sort Example
============================= Split
3
8
3
3
3
8
6
6
8
6
8
6
Steps ==========================
1
8
1
1
3
1
2
6
3
2
1
7
1
7
1
7
============================ Merge
3
7
2
4
5
2
4
5
2
4
5
4
Steps =========================
6
2
8
2
4
5
5
7
4
4
6
5
5
7
7
8
Merge Sort
●
●
●
Merge sort is an example of a divide-andconquer algorithm.
A sorting algorithm that modifies an existing
array, such as insertion sort, is called an inplace sort (sort inside the array).
Merge sort is not an in-place sort.
Merge Sort
Merge Sort
●
The merge() method combines two sorted
arrays into one longer sorted array.
Merge Sort
●
merge() method takes linear time in the total
length of the resulting array.
Merge Sort
●
mergeSortHelper recurrence.
Quicksort
●
Another divide-and-conquer sorting algorithm.
●
Here's the plan:
–
If there are zero or one number to sort, do nothing.
–
Otherwise, partition the region into “small” and Large”
numbers, moving the small numbers to the left and the
large numbers to the right. Recursively sort each
section. The entire array is now sorted.
Quicksort
●
●
●
Partitioning algorithm begins by choosing some
array element as the pivot.
Usually choose the rightmost element in each
partition as the pivot.
Numbers less than or equal to the pivot are
considered small, while numbers greater than
the pivot are considered large.
Quicksort
●
As it runs, the algorithm maintains four regions:
–
–
–
–
●
Those numbers known to be small.
Those numbers know to be large.
Those numbers which haven't been examined yet.
The pivot itself.
The four regions:
–
data[bottom] through data[firstAfterSmall - 1] are known to
be small.
–
data[firstAfterSmall] through data[i-1] are known to be large.
–
data[i] through data[top-1] have not yet been examined.
–
The pivot is at data[top].
Quicksort
Quick Sort Example
3
8
6
1
7
2
5
4
3
1
2
8
7
6
5
4
3
1
2
4
7
6
5
8
3
1
2
1
3
2
1
2
1
2
3
3
4
7
6
5
5
6
7
5
6
8
7
The 8 integers are sorted!
Quicksort
Quicksort
Quicksort
●
●
●
Partition() is linear time
Best case O(n log n), but partition() might not divide
the region evenly in half.
Worst case:
Quicksort
●
Quicksort is better than insertion sort, but
not as good as merge sort.
–
Since it has a low constant factor associated
with its running time, and operates in place,
Quicksort is sometimes used instead of merge
sort when n is not expected to be very large.
Quicksort
●
Class java.util.Arrays has several overloaded
versions of the static method sort().
–
The ones for arrays of primitive types use an
optimized version of Quicksort that makes the
worst-case behavior unlikely.
–
The version for arrays of objects uses merge sort.
●
●
●
The difference has to do with the fact that two objects
that are equals() may not be identical.
If a sort keeps such elements in the same order as the
original array, the sort is said to be stable.
Merge sort is stable, but Quicksort is not.
Avoiding Recursion
●
All other things being equal, it is better to
avoid recursion.
–
Every time we invoke a method, we have to
push a frame onto the call stack.
–
This uses both time and memory.
–
These optimizations may improve efficiency at
the expense of program clarity; this trade off is
not always worthwhile.
Avoiding Recursion
●
If we fail to include a base case in a recursive method:
java.lang.StackOverflowError
–
●
We run out of memory, the stack overflows.
An iterative program which fails to include a proper stopping
condition will simply run forever.
Avoiding Recursion
●
●
Tail recursive algorithms are easy to convert to
iteration.
In tail recursive algorithms the recursive invocation
is the very last thing we do.
Avoiding Recursion
●
Instead of recurring with new arguments we
simply change the values of the existing
arguments and go back to the beginning.
Avoiding Recursion
●
Using the loop test to handle the base case
equivalent.
Avoiding Recursion
●
●
●
If a recursive algorithm is not tail recursive,
the only way to convert it into iterative form
may be to manage our own version of the
call stack.
This is complicated and, since it does not
eliminate stack manipulation, rarely worth
the effort.
Certain non-tail-recursive algorithms can be
made far more efficient by converting them
into iterative form.
Avoiding Recursion
●
Fibonacci Sequence:
–
–
–
Begin with a pair of newborn rabbits, one male
and one female.
Beginning in its second month of life, each pair
produces another pair every month.
Assuming the rabbits never die, how many
pairs will there be after n months?
Avoiding Recursion
●
●
Woefully inefficient.
F(n) Θ(Φn), where Φ (the lower-case Greek letter phi)
is the golden ratio, roughly 1.618.
●
Not tail recursive.
●
fibo() does a lot of redundant work.
Avoiding Recursion
Iterative Fibonacci Program
// An iterative program to generate the Fibonacci numbers.
// Let n = 6.
public class IterativeFibonacci {
public static void main(String args[]) {
int oneBefore=1, twoBefore=0, fiboNum=0;
for (int i=2; i<=6; i++) {
fiboNum = oneBefore + twoBefore;
oneBefore = fiboNum;
twoBefore = oneBefore;
}
System.out.println("The Fibonacci(6) is:" + fiboNum);
}
}
Avoiding Recursion
●
Dynamic programming
–
–
Technique for improving the efficiency of recursive
algorithms that do redundant work.
Solutions to subproblems are stored (e.g. in an array) so
that they can be looked up rather than recomputed.
Summary
●
●
●
To solve a problem recursively, we define a
simple base case and a recursive case.
Recursive case solves the problems in terms of
subproblems which are closer to the base case.
Recursive algorithms are analyzed using
recurrences.
–
To solve a recurrence, expand it into a recursion tree,
then determine the number of steps at each level and
the number of levels.
–
Plug the solution into the recurrence to verify it is
correct.
Summary
●
Merge sort and Quicksort
–
Both of these are divide-and-conquer algorithms
which divide the data into parts, recursively sort the
parts, and then recombine the solutions.
–
Merge sort, the hard work is in the recombining.
●
–
Θ(n log n)
Quicksort, the hard work is in the dividing.
●
●
Θ(n log n) on average, its worst-case running time is
quadratic.
Simple improvements can make the worst case unlikely.
Summary
●
Recursion allows for the design of powerful,
elegant algorithms, but it uses up time and
space for the call stack.
–
–
–
Efficiency can sometimes be improved by
eliminating recursion.
A tail-recursive algorithm can easily be converted
into a loop.
If the algorithm is only returning a value (as
opposed to modifying an existing data structure),
redundant computation can be avoided by storing
the results of previous invocation in a table (array).
Chapter 9 Self-Study Homework
●
Pages: 231-248
●
Do the following Exercises:
9.1, 9.2, 9.5, 9.6, 9.7, 9.18.