Transcript Recursion

Chapter 5
Recursion
Data Structures Using Java
1
Chapter Objectives
• Learn about recursive definitions
• Explore the base case and the general case of a
recursive definition
• Discover what a recursive algorithm is
• Learn about recursive methods
• Explore how to use recursive methods to
implement recursive algorithms
• Learn how recursion implements backtracking
Data Structures Using Java
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
Data Structures Using Java
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
Data Structures Using Java
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
Data Structures Using Java
5
Tracing a Recursive Method
Recursive method
– Has unlimited copies of itself
– Every recursive call has
• its own code
• own set of parameters
• own set of local variables
Data Structures Using Java
6
Tracing a Recursive Method
After completing recursive call
• Control goes back to 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
Data Structures Using Java
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
Data Structures Using Java
8
Designing Recursive Methods
• Understand problem requirements
• Determine limiting conditions
• Identify base cases
Data Structures Using Java
9
Designing Recursive Methods
• Provide direct solution to each base case
• Identify general case(s)
• Provide solutions to general cases in terms
of smaller versions of itself
Data Structures Using Java
10
Recursive Factorial Function
public static int fact(int num)
{
if(num == 0)
return 1;
else
return num * fact(num – 1);
}
Data Structures Using Java
11
Recursive Factorial Trace
Data Structures Using Java
12
Recursive Implementation:
Largest Value in Array
public static int largest(int list[], int lowerIndex, int
upperIndex)
{
int max;
if(lowerIndex == upperIndex)
//the size of the sublist is 1
return list[lowerIndex];
else
{
max = largest(list, lowerIndex + 1, upperIndex);
if(list[lowerIndex] >= max)
return list[lowerIndex];
else
return max;
}
}
Data Structures Using Java
13
Execution of largest(list, 0, 3)
Data Structures Using Java
14
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);
}
Data Structures Using Java
15
Execution of rFibonacci(2,3,5)
Data Structures Using Java
16
Towers of Hanoi Problem with
Three Disks
Data Structures Using Java
17
Towers of Hanoi: Three Disk
Solution
Data Structures Using Java
18
Towers of Hanoi: Three Disk
Solution
Data Structures Using Java
19
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 “ +
needle1 + “ to “ + needle3 + ".“);
moveDisks(count - 1, needle2, needle3, needle1);
}
}
Data Structures Using Java
20
Decimal to Binary: Recursive
Algorithm
public static void decToBin(int num,
int base)
{
if(num > 0)
{
decToBin(num/base, base);
System.out.println(num % base);
}
}
Data Structures Using Java
21
Execution of decToBin(13,2)
Data Structures Using Java
22
Sierpinski Gasket
Suppose that you have the triangle ABC.
Determine the midpoints P,Q, and R of the sides AB, AC, and
BC, respectively.
Draw the lines PQ,QR, and PR.
This creates three triangles APQ, BPR, and CRQ of similar
shape as the triangle ABC.
Process of finding midpoints of sides, then drawing lines
through midpoints on triangles APQ, BPR, and CRQ is called
a Sierpinski gasket of order or level 0, level 1, level 2, and
level 3, respectively.
Data Structures Using Java
23
Sierpinski Gaskets of Various
Orders
Data Structures Using Java
24
Programming Example:
Sierpinski Gasket
• Input: non-negative 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
Data Structures Using Java
25
Recursive Algorithm to Draw
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);
}
}
Data Structures Using Java
26
Programming Example:
Sierpinski Gasket Input
Data Structures Using Java
27
Programming Example:
Sierpinski Gasket Input
Data Structures Using Java
28
Recursion or Iteration?
• Two ways to solve particular problem
– Iteration
– Recursion
• Iterative control structures: uses looping to
repeat a set of statements
• Tradeoffs between two options
– Sometimes recursive solution is easier
– Recursive solution is often slower
Data Structures Using Java
29
8-Queens Puzzle
Place 8 queens on a chessboard (8 X 8 square
board) so that no two queens can attack each
other. For any two queens to be non-attacking,
they cannot be in the same row, same column,
or same diagonals.
Data Structures Using Java
30
Backtracking Algorithm
• Attempts to find solutions to a problem by
constructing partial solutions
• Makes sure that any partial solution does
not violate the problem requirements
• Tries to extend partial solution towards
completion
Data Structures Using Java
31
Backtracking Algorithm
• If it is determined that partial solution
would not lead to solution
– partial solution would end in dead end
– algorithm backs up by removing the most
recently added part and then tries other
possibilities
Data Structures Using Java
32
Solution to 8-Queens Puzzle
Data Structures Using Java
33
4-Queens Puzzle
Data Structures Using Java
34
4-Queens Tree
Data Structures Using Java
35
8 X 8 Square Board
Data Structures Using Java
36
Chapter Summary
•
•
•
•
•
Recursive Definitions
Recursive Algorithms
Recursive methods
Base cases
General cases
Data Structures Using Java
37
Chapter Summary
•
•
•
•
•
•
Tracing recursive methods
Designing recursive methods
Varieties of recursive methods
Recursion vs. Iteration
Backtracking
N-Queens puzzle
Data Structures Using Java
38