Transcript Chapter 14: Recursion

Chapter 14: Recursion
Java Programming:
Program Design Including Data Structures
Chapter Objectives
 Learn about recursive definitions
 Explore the base case and the general case of a
recursive definition
 Learn about recursive algorithms
 Learn about recursive methods
 Become aware of direct and indirect recursion
 Explore how to use recursive methods to implement
recursive algorithms
Java Programming: Program Design Including Data Structures
2
Recursion or Iteration?
 Many problem can be solved by building an
iterative control structures  using a looping
structure to repeat a set of statements:
 while, for, or do … while
 different approach?  a recursion
 Designing a recursive method
 Using an iterative control structure
 In addition, a selection control structure is used to
control the repeated calls in recursion.
Java Programming: Program Design Including Data Structures
3
Recursion or Iteration?
 Tradeoffs between two options:
 Sometimes recursive solution is easier
 Recursive solution is often slower
 No simple answer!  consider the nature of the
problem and system efficiency.
Java Programming: Program Design Including Data Structures
4
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: Program Design Including Data Structures
5
Tracing a Recursive Method
 Recursive method:
 Has unlimited copies of itself
 Every recursive call has its own:
 Code
 Set of parameters
 Set of local variables
 Every recursive call requires that the system
allocate memory space for its parameters and local
variables
Java Programming: Program Design Including Data Structures
6
Tracing a Recursive Method
 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: Program Design Including Data Structures
7
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
 In base case, the solution is obtained directly and
stops the recursion.
 Implemented using recursive methods
Java Programming: Program Design Including Data Structures
8
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: Program Design Including Data Structures
9
Designing Recursive Methods
 Understand problem nature and requirements
 Determine limiting conditions
 Identify base cases
 Provide direct solution to each base case
 Identify general (recursive) cases
 Provide solutions to general (recursive) cases in
terms of smaller versions of general cases
Java Programming: Program Design Including Data Structures
10
Recursive Factorial Method
public static int fact(int num)
{
if (num = = 0)
return 1;
else
return num * fact(num – 1);
}
Java Programming: Program Design Including Data Structures
11
Recursive Factorial Method
(continued)
Java Programming: Program Design Including Data Structures
12
Largest Value in Array
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: Program Design Including Data Structures
13
Largest Value in Array (continued)
list = {5, 10, 12, 8}
Java Programming: Program Design Including Data Structures
14
Recursive Fibonacci
where
a and b: the first two numbers of the Fibonacci sequence
n: the desired nth Fibonacci number
Java Programming: Program Design Including Data Structures
15
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: Program Design Including Data Structures
16
rFibNum(2,3,5)
Java Programming: Program Design Including Data Structures
17
Towers of Hanoi: Three Disk
Problem
Java Programming: Program Design Including Data Structures
18
Towers of Hanoi: Three Disk
Solution
Java Programming: Program Design Including Data Structures
19
Towers of Hanoi: Three Disk
Solution
Java Programming: Program Design Including Data Structures
20
Tower of Hanoi:
Recursive Algorithm
 Identify base cases
 When n = 1 : move the disk from needle 1 to needle 3
 Identify general (recursive) cases
 Provide solutions to general cases in terms of smaller
versions of general cases
Java Programming: Program Design Including Data Structures
21
Recursive Solution
// Base solution:
//
Move a single disk from needle 1 to needle 3
// General solution:
//
1. Move top (count-1) disks from needle1 to needle 2
//
using intermediate needle 3
//
2. Move disk count from needle 1 to needle 3
//
3. Move the top (count-1) disks from needle 2
//
to needle 3 using intermediate needle 1
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: Program Design Including Data Structures
22
Programming Example:
Decimal to Binary
public static void decToBin(int num,
int base) {
if (num > 0)
{
decToBin(num / base, base);
System.out.print(num % base);
}
}
Java Programming: Program Design Including Data Structures
23
Java Programming: Program Design Including Data Structures
24
Programming Example: Sierpinski
Gasket
Java Programming: Program Design Including Data Structures
25
Programming Example:
Sierpinski Gasket (continued)
 Input: Non-negative integer that indicates level of
Sierpinski gasket
 Output: Triangle shape that displays a Sierpinski
gasket of the given order
 Solution includes:
 Recursive method drawSierpinski
 Method to find midpoint of two points
Java Programming: Program Design Including Data Structures
26
Sierpinski Gasket
 Base case: If the level is 1, draw the first triangle
 Recursive case: If level > 1, for each triangle, find
the midpoints of the sides and draw lines through
those points.
private Point midPoint(Point pOne, Point pTwo) {
Point mid = new Point((pOne.x + pTwo.x)/2,
(pOne.y + pTwo.y)/2);
return mid;
}
Java Programming: Program Design Including Data Structures
27
Sierpinski Gasket
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: Program Design Including Data Structures
28
Sierpinski Gasket (continued)
Java Programming: Program Design Including Data Structures
29
Chapter Summary
 Recursive definitions
 Recursive algorithms
 Recursive methods
 Base cases
 General cases
Java Programming: Program Design Including Data Structures
30
Chapter Summary (continued)
 Tracing recursive methods
 Designing recursive methods
 Varieties of recursive methods
 Recursion vs. iteration
 Various recursive functions
Java Programming: Program Design Including Data Structures
31