Transcript Chapter 14

Java Programming: From Problem
Analysis to Program Design, 4e
Chapter 13
Recursion
Chapter Objectives
• Learn about recursive definitions
• Explore the base case and the general case
of a recursive definition
• Learn about recursive algorithms
Java Programming: From Problem Analysis to Program Design, 4e
2
Chapter Objectives (continued)
• Learn about recursive methods
• Become aware of direct and indirect
recursion
• Explore how to use recursive methods to
implement recursive algorithms
Java Programming: From Problem Analysis to Program Design, 4e
3
Recursive Definitions
• Recursion
– Process of solving a problem by reducing it to
smaller versions of itself
• Recursive definition
– Definition in which a problem is expressed in
terms of a smaller version of itself
– Has one or more base cases
Java Programming: From Problem Analysis to Program Design, 4e
4
Recursive Definitions (continued)
Java Programming: From Problem Analysis to Program Design, 4e
5
Recursive Definitions (continued)
• Recursive algorithm
– Algorithm that finds the solution to a given problem
by reducing the problem to smaller versions of itself
– Has one or more base cases
– Implemented using recursive methods
• Recursive method
– Method that calls itself
• Base case
– Case in recursive definition in which the solution is
obtained directly
– Stops the recursion
Java Programming: From Problem Analysis to Program Design, 4e
6
Recursive Definitions (continued)
• General solution
– Breaks problem into smaller versions of itself
• General case
– Case in recursive definition in which a smaller
version of itself is called
– Must eventually be reduced to a base case
Java Programming: From Problem Analysis to Program Design, 4e
7
Tracing a Recursive Method
• Recursive method
– Logically, you can think of a recursive method
having unlimited copies of itself
– Every recursive call has its own:
• Code
• Set of parameters
• Set of local variables
Java Programming: From Problem Analysis to Program Design, 4e
8
Tracing a Recursive Method
(continued)
• After completing a recursive call
– Control goes back to the calling environment
– Recursive call must execute completely before
control goes back to previous call
– Execution in previous call begins from point
immediately following recursive call
Java Programming: From Problem Analysis to Program Design, 4e
9
Recursive Definitions
• Directly recursive: a method that calls itself
• Indirectly recursive: a method that calls another
method and eventually results in the original
method call
• Tail recursive method: recursive method in
which the last statement executed is the
recursive call
• Infinite recursion: the case where every
recursive call results in another recursive call
Java Programming: From Problem Analysis to Program Design, 4e
10
Designing Recursive Methods
• Understand problem requirements
• Determine limiting conditions
• Identify base cases
Java Programming: From Problem Analysis to Program Design, 4e
11
Designing Recursive Methods
(continued)
• Provide direct solution to each base case
• Identify general case(s)
• Provide solutions to general cases in terms
of smaller versions of general cases
Java Programming: From Problem Analysis to Program Design, 4e
12
Recursive Factorial Method
public static int fact(int num)
{
if (num = = 0)
return 1;
else
return num * fact(num – 1);
}
Java Programming: From Problem Analysis to Program Design, 4e
13
Recursive Factorial Method (continued)
Java Programming: From Problem Analysis to Program Design, 4e
14
Largest Value in Array
Java Programming: From Problem Analysis to Program Design, 4e
15
Largest Value in Array (continued)
•
•
if the size of the list is 1
the largest element in the list is the only element in the list
else
to find the largest element in list[a]...list[b]
a. find the largest element in list[a + 1]...list[b]
and call it max
b. compare list[a] and max
if (list[a] >= max)
the largest element in list[a]...list[b] is
list[a]
else
the largest element in list[a]...list[b] is max
Java Programming: From Problem Analysis to Program Design, 4e
16
Largest Value in Array (continued)
public static int largest(int[] list,
int lowerIndex,
int upperIndex)
{
int max;
if (lowerIndex == upperIndex)
return list[lowerIndex];
else
{
max = largest(list, lowerIndex + 1, upperIndex);
if (list[lowerIndex] >= max)
return list[lowerIndex];
else
return max;
}
}
Java Programming: From Problem Analysis to Program Design, 4e
17
Execution of largest
(list, 0, 3)
Java Programming: From Problem Analysis to Program Design, 4e
18
Execution of largest (list, 0, 3)
Java Programming: From Problem Analysis to Program Design, 4e
19
Recursive Fibonacci
Java Programming: From Problem Analysis to Program Design, 4e
20
Recursive Fibonacci (continued)
public static int rFibNum(int a, int b,
int n)
{
if (n == 1)
return a;
else if (n == 2)
return b;
else
return rFibNum(a, b, n -1) +
rFibNum(a, b, n - 2);
}
Java Programming: From Problem Analysis to Program Design, 4e
21
Recursive Fibonacci (continued)
Java Programming: From Problem Analysis to Program Design, 4e
22
Towers of Hanoi Problem with
Three Disks
Java Programming: From Problem Analysis to Program Design, 4e
23
Towers of Hanoi: Three Disk
Solution
Java Programming: From Problem Analysis to Program Design, 4e
24
Towers of Hanoi: Three Disk Solution
(continued)
Java Programming: From Problem Analysis to Program Design, 4e
25
Towers of Hanoi: Recursive Algorithm
public static void moveDisks(int count,
int needle1, int needle3, int needle2)
{
if (count > 0)
{
moveDisks(count - 1, needle1,
needle2, needle3);
System.out.println("Move disk " + count
+ " from needle "
+ needle1 + " to needle "
+ needle3 + ". ");
moveDisks(count - 1, needle2,
needle3, needle1);
}
}
Java Programming: From Problem Analysis to Program Design, 4e
26
Recursion or Iteration?
• Two ways to solve particular problem
– Iteration
– Recursion
• Iterative control structures: use looping to
repeat a set of statements
• Tradeoffs between two options
– Sometimes recursive solution is easier
– Recursive solution is often slower
Java Programming: From Problem Analysis to Program Design, 4e
27
Programming Example:
Decimal to Binary
Java Programming: From Problem Analysis to Program Design, 4e
28
Java Programming: From Problem Analysis to Program Design, 4e
29
Sierpinski Gaskets of Various Orders
Java Programming: From Problem Analysis to Program Design, 4e
30
Programming Example:
Sierpinski Gasket
• Input: nonnegative integer indicating level
of Sierpinski gasket
• Output: triangle shape displaying a
Sierpinski gasket of the given order
• Solution includes:
– Recursive method drawSierpinski
– Method to find midpoint of two points
Java Programming: From Problem Analysis to Program Design, 4e
31
Programming Example:
Sierpinski Gasket (continued)
private void drawSierpinski(Graphics g, int lev,
Point p1, Point p2, Point p3)
{
Point midP1P2;
Point midP2P3;
Point midP3P1;
if (lev > 0)
{
g.drawLine(p1.x, p1.y, p2.x, p2.y);
g.drawLine(p2.x, p2.y, p3.x, p3.y);
g.drawLine(p3.x, p3.y, p1.x, p1.y);
midP1P2 = midPoint(p1, p2);
midP2P3 = midPoint(p2, p3);
midP3P1 = midPoint(p3, p1);
drawSierpinski(g, lev - 1, p1, midP1P2,
midP3P1);
drawSierpinski(g, lev - 1, p2, midP2P3,
midP1P2);
drawSierpinski(g, lev - 1, p3,
midP3P1, midP2P3);
}
} Java Programming: From Problem Analysis to Program Design, 4e
32
Programming Example: Sierpinski
Gasket (continued)
Java Programming: From Problem Analysis to Program Design, 4e
33
Chapter Summary
•
•
•
•
•
Recursive definitions
Recursive algorithms
Recursive methods
Base cases
General cases
Java Programming: From Problem Analysis to Program Design, 4e
34
Chapter Summary (continued)
•
•
•
•
•
Tracing recursive methods
Designing recursive methods
Varieties of recursive methods
Recursion vs. iteration
Various recursive functions explored
Java Programming: From Problem Analysis to Program Design, 4e
35