Transcript Chapter 1

Chapter 14: Recursion
Java Programming:
From Problem Analysis to Program Design,
Second Edition
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: From Problem Analysis to Program Design, Second Edition
2
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, Second Edition
3
Recursive Definitions
 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, Second Edition
4
Recursive Definitions
 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, Second Edition
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
Java Programming: From Problem Analysis to Program Design, Second Edition
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: From Problem Analysis to Program Design, Second Edition
7
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, Second Edition
8
Designing Recursive Methods
 Understand problem requirements.
 Determine limiting conditions.
 Identify base cases.
Java Programming: From Problem Analysis to Program Design, Second Edition
9
Designing Recursive Methods
 Provide direct solution to each base case.
 Identify general cases.
 Provide solutions to general cases in terms of
smaller versions of general cases.
Java Programming: From Problem Analysis to Program Design, Second Edition
10
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, Second Edition
11
Recursive Factorial Method
Java Programming: From Problem Analysis to Program Design, Second Edition
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: From Problem Analysis to Program Design, Second Edition
13
Largest Value in Array
Java Programming: From Problem Analysis to Program Design, Second Edition
14
Recursive Fibonacci
Java Programming: From Problem Analysis to Program Design, Second Edition
15
Recursive Fibonacci
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, Second Edition
16
Recursive Fibonacci
Java Programming: From Problem Analysis to Program Design, Second Edition
17
Towers of Hanoi: Three Disk Problem
Java Programming: From Problem Analysis to Program Design, Second Edition
18
Towers of Hanoi: Three Disk Solution
Java Programming: From Problem Analysis to Program Design, Second Edition
19
Towers of Hanoi: Three Disk Solution
Java Programming: From Problem Analysis to Program Design, Second Edition
20
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, Second Edition
21
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, Second Edition
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: From Problem Analysis to Program Design, Second Edition
23
Programming Example: Decimal to Binary
Java Programming: From Problem Analysis to Program Design, Second Edition
24
Programming Example: Sierpinski Gasket
Java Programming: From Problem Analysis to Program Design, Second Edition
25
Programming Example:
Sierpinski Gasket
 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: From Problem Analysis to Program Design, Second Edition
26
Programming Example: 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: From Problem Analysis to Program Design, Second Edition
27
Programming Example: Sierpinski Gasket
Java Programming: From Problem Analysis to Program Design, Second Edition
28
Chapter Summary
 Recursive definitions
 Recursive algorithms
 Recursive methods
 Base cases
 General cases
Java Programming: From Problem Analysis to Program Design, Second Edition
29
Chapter Summary
 Tracing recursive methods
 Designing recursive methods
 Varieties of recursive methods
 Recursion vs. iteration
 Various recursive functions
Java Programming: From Problem Analysis to Program Design, Second Edition
30