Transcript chapter 1

CHAPTER 17
RECURSION
CHAPTER GOALS
• To learn about the method of recursion
• To understand the relationship between recursion
and iteration
• To analysis problems that are much easier to
solve by recursion than by iteration
• To learn to think recursively
• To be able to use recursive helper methods
• To understand when the use of recursion affects
the efficiency of an algorithm
Triangle Numbers
• Compute the area of a triangle of width
n
• Assume each [] square has an area of 1
• Also called the nth triangle number
The Third Triangle Number
• The third triangle number is 6
[]
[] []
[] [] []
Outline of Triangle Class
public class Triangle
{
public Triangle(int aWidth)
{
width = aWidth;
}
public int getArea()
{
...
}
private int width;
}
Handling Triangle of Width 1
• The triangle consists of a single square
• Its area is 1
• Add the code to getArea method for width
public int getArea()
{
if (width == 1) return 1;
}
Handling General Case
[]
[] []
[] [] []
[] [] [] []
• Assume we know the area of the smaller, colored triangle
• Area of larger triangle can be calculated as:
smallerArea + width
• To get the area of the smaller triangle
o make a smaller triangle and ask it for its area
Triangle smallerTriangle = new Triangle(width - 1);
int smallerArea = smallerTriangle.getArea();
Completed getArea method
public int getArea()
{
if (width == 1) return 1;
Triangle smallerTriangle = new
Triangle(width - 1);
int smallerArea =
smallerTriangle.getArea();
smallerArea + width;
}
return
Computing the area of a triangle
with width 4
• getArea method makes a smaller triangle of width 3
• It calls getArea on that triangle
– That method makes a smaller triangle of width 2
• It calls getArea on that triangle
– That method makes a smaller triangle of width 1
– It calls getArea on that triangle
• That method returns 1
– The method returns smallerArea + width = 1 + 2 = 3
• The method returns smallerArea + width = 3 + 3 = 6
• The method returns smallerArea + width = 6 + 4 = 10
Recursion
• A recursive computation solves a problem by
using the solution
of the same problem with simpler input
• For recursion to terminate,
there must be special cases for the simplest
inputs.
• To complete our Triangle example, we must
handle width <= 0
• Add this line to the getArea method
if (width <= 0)
return 0;
File Triangle.java
01: /**
02: A triangular shape composed of stacked unit squares like this:
03: []
04: [][]
05: [][][]
06: . . .
07: */
08: public class Triangle
09: {
10: /**
11:
Constructs a triangular shape
12:
@param aWidth the width (and height) of the triangle
13: */
14: public Triangle(int aWidth)
15: {
16:
width = aWidth;
17: }
18:
19: /**
20:
Computes the area of the triangle.
21:
@return the area
22: */
23: public int getArea()
24: {
25:
if (width <= 0) return 0;
26:
if (width == 1) return 1;
27:
Triangle smallerTriangle = new Triangle(width - 1);
28:
int smallerArea = smallerTriangle.getArea();
29:
return smallerArea + width;
30: }
31:
32: private int width;
33: }
TriangleTest.java
01: import javax.swing.JOptionPane;
02:
03: public class TriangleTest
04: {
05: public static void main(String[] args)
06: {
07:
String input = JOptionPane.showInputDialog("Enter width");
08:
int width = Integer.parseInt(input);
09:
Triangle t = new Triangle(width);
10:
int area = t.getArea();
11:
System.out.println("Area = " + area);
12: }
13: }
Permutations of a String
• Design a class that will list all permutations
of a string
• A permutation is a rearrangement of the
letters
• The string "eat" has six permutations
"eat"
"eta"
"aet"
"tea"
"tae"
Public Interface of
PermutationGenerator
class PermutationGenerator
{
public PermutationGenerator(String s) { . . . }
public String nextPermutation() {. . . }
public boolean hasMorePermutations() { . . . }
}
File
PermutationGeneratorTest.java
01: /**
02: This program tests the permutation generator.
03: */
04: public class PermutationGeneratorTest
05: {
06: public static void main(String[] args)
07: {
08:
PermutationGenerator generator
09:
= new PermutationGenerator("eat");
10:
while (generator.hasMorePermutations())
11:
System.out.println(generator.nextPermutation());
12: }
13: }
To Generate All Permutations
• Generate all permutations that start with 'e' ,
then 'a' then 't'
• To generate permutations starting with 'e', we
need to find all permutations of "at"
• This is the same problem with simpler inputs.
• Use recursion
To Generate All Permutations
• nextPermutaion
method returns one permutation at a
time
• PermutationGenerator remembers its state
o The string we are permuting (word)
o Position of the current character (current)
o PermutationGenerator of the substring (tailGenerator)
asks tailGenerator for its next
permutation and returns
• nextPermutation
word.charAt(current) + tailGenerator.nextPermutation();
Handling the Special Case
• When the tail generator runs out of
permutations, we need to:
o Increment the current position
o Compute the tail string that contains all
letters
except for the current one
o Make a new permutation generator for
the tail string
File PermutationGenerator.java
01: /**
02: This class generates permutations of a word.
03: */
04: class PermutationGenerator
05: {
06: /**
07:
Constructs a permutation generator.
08:
@param aWord the word to permute
09: */
10: public PermutationGenerator(String aWord)
11: {
12:
word = aWord;
13:
current = 0;
14:
if (word.length() > 1)
15:
tailGenerator = new PermutationGenerator(word.substring(1));
16:
System.out.println("Generating " + word );
17: }
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:
33:
34:
35:
36:
37:
38:
/**
Computes the next permutation of the word.
@return the next permutation
*/
public String nextPermutation()
{
if (word.length() == 1)
{
current++;
return word;
}
String r = word.charAt(current) + tailGenerator.nextPermutation();
if (!tailGenerator.hasMorePermutations())
{
current++;
if (current < word.length())
{
String tailString = word.substring(0, current)
39:
+ word.substring(current + 1);
40:
tailGenerator = new PermutationGenerator(tailString);
41:
}
42:
}
43:
44:
return r;
45: }
46:
47: /**
48:
Tests whether there are more permutations.
49:
@return true if more permutations are available
50: */
51: public boolean hasMorePermutations()
52: {
53:
return current < word.length();
54: }
55:
56: private String word;
57: private int current;
58: private PermutationGenerator tailGenerator;
59: }
Recursive Helper Method
• The public boolean method isPalindrone
calls helper method
isPalindrome(int start, int end)
• Helper method skips over matching letter
pairs and non-letters and calls itself
recursively
Recursive
Helper
Method
public boolean isPalindrome(int start int end)
{
//separate case for substrings of length 0 or 1
if (start>=end) return true;
//get first and last character, converted to lowercase
char first = Character.toLowerCase(text.charAt(start));
char last = Character.toLowerCase(text.charAt(end));
if ((Character.isLetter(first) && Character.isLetter(last))
{
if (first == last)
{
//test substring that doesn't contain the matching letters
return isPalindrome(start +1, end -1);
}
else
return false;
}
else if (!Character.isLetter(last))
{
//test substring that doesn't contain last character
return isPalindrome(start, end -1);
}
else
{
//test substring that doesn't contain first character
return isPalindrome(start + 1, end);
}
Using Mutual Recursion
• Problem: to compute the value of
arithmetic expressions such as
3+4*5
(3 + 4) * 5
1 - (2 - (3 - (4 - 5)))
Syntax Diagram for Evaluating
and Expression
Syntax Tree for Two Expressions
Mutually Recursive Methods
• Implement 3 methods that call each
other recursively
o getExpressionValue
o getTermValue
o getFactorValue
File Evaluator.java
01: /**
02: A class that can compute the value of an arithmetic expression.
03: */
04: public class Evaluator
05: {
06: /**
07:
Constructs an evaluator.
08:
@param anExpression a string containing the expression
09:
to be evaluated.
10: */
11: public Evaluator(String anExpression)
12: {
13:
tokenizer = new ExpressionTokenizer(anExpression);
14: }
15:
16: /**
17:
Evaluates the expression.
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:
33:
34:
35:
36:
37:
@return the value of the expression.
*/
public int getExpressionValue()
{
int value = getTermValue();
boolean done = false;
while (!done)
{
String next = tokenizer.peekToken();
if ("+".equals(next) || "-".equals(next))
{
tokenizer.nextToken();
int value2 = getTermValue();
if ("+".equals(next)) value = value + value2;
else value = value - value2;
}
else done = true;
}
return value;
}
38:
39:
40:
41:
42:
43:
44:
45:
46:
47:
48:
49:
50:
51:
52:
53:
54:
55:
56:
57:
/**
Evaluates the next term found in the expression.
@return the value of the term.
*/
public int getTermValue()
{
int value = getFactorValue();
boolean done = false;
while (!done)
{
String next = tokenizer.peekToken();
if ("*".equals(next) || "/".equals(next))
{
tokenizer.nextToken();
int value2 = getFactorValue();
if ("*".equals(next)) value = value * value2;
else value = value / value2;
}
else done = true;
58:
59:
60:
61:
62:
63:
64:
65:
66:
67:
68:
69:
70:
71:
72:
73:
74:
75:
76:
77:
}
return value;
}
/**
Evaluates the next factor found in the expression.
@return the value of the factor.
*/
public int getFactorValue()
{
int value;
String next = tokenizer.peekToken();
if ("(".equals(next))
{
tokenizer.nextToken();
value = getExpressionValue();
next = tokenizer.nextToken(); // read ")"
}
else
value = Integer.parseInt(tokenizer.nextToken());
78:
return value;
79: }
80:
81: private ExpressionTokenizer tokenizer;
82: }
File
ExpressionTokenizer.java
01: /**
02: This class breaks up a string describing an expression
03: into tokens: numbers, parentheses, and operators
04: */
05: public class ExpressionTokenizer
06: {
07: /**
08:
Constructs a tokenizer.
09:
@param anInput the string to tokenize
10: */
11: public ExpressionTokenizer(String anInput)
12: {
13:
input = anInput;
14:
start = 0;
15:
end = 0;
16:
nextToken();
17: }
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:
33:
34:
35:
36:
37:
/**
Peeks at the next token without consuming it.
@return the next token or null if there are no more tokens
*/
public String peekToken()
{
if (start >= input.length()) return null;
else return input.substring(start, end);
}
/**
Gets the next token and moves the tokenizer to the
following token.
@return the next token or null if there are no more tokens
*/
public String nextToken()
{
String r = peekToken();
start = end;
38:
if (start >= input.length()) return r;
39:
if (Character.isDigit(input.charAt(start)))
40:
{
41:
end = start + 1;
42:
while (end < input.length() && Character.isDigit(input.charAt(end)))
43:
end++;
44:
}
45:
else
46:
end = start + 1;
47:
return r;
48: }
49:
50: private String input;
51: private int start;
52: private int end;
53: }
File
EvaluatorTest.java
01: import javax.swing.JOptionPane;
02:
03: /**
04: This program tests the expression evaluator.
05: */
06: public class EvaluatorTest
07: {
08: public static void main(String[] args)
09: {
10:
String input = JOptionPane.showInputDialog("Enter an expression:");
11:
Evaluator e = new Evaluator(input);
12:
int value = e.getExpressionValue();
13:
System.out.println(input + "=" + value);
14:
System.exit(0);
15: }
16: }
Fibonacci Sequence
• Fibonacci sequence is a sequence of
numbers defined by
f1 = 1
f2 = 1
fn = fn-1 + fn-2
• First ten terms
1, 1, 2, 3, 5, 8, 13, 21, 34, 55
The Efficiency of Recursion
• You can generate the Fibonacci
series using either recursion or
iteration
o Both are conceptually easy to
understand and program
o Iterative solution is much faster
The Efficiency of Recursion
• Palindrome test can be
implemented as either recursion
or iteration
o Both are easy to program
o Both run about the same speed
The Efficiency of Recursion
• Permutation generator can be
solved using either recursion or
iteration
o Recursive solution is
dramatically easier to understand
and implement
o Both run at about the same
speed
File FibTest.java
01: import javax.swing.JOptionPane;
02:
03: /**
04: This program computes Fibonacci numbers using a recursive
05: method.
06: */
07: public class FibTest
08: {
09: public static void main(String[] args)
10: {
11:
String input = JOptionPane.showInputDialog("Enter n: ");
12:
int n = Integer.parseInt(input);
13:
14:
for (int i = 1; i <= n; i++)
15:
{
16:
int f = fib(i);
17:
System.out.println("fib(" + i + ") = " + f);
18:
}
19:
System.exit(0);
20: }
21:
22: /**
23:
Computes a Fibonacci number.
24:
@param n an integer
25:
@return the nth Fibonacci number
26: */
27: public static int fib(int n)
28: {
29:
if (n <= 2) return 1;
30:
else return fib(n - 1) + fib(n - 2);
31: }
32: }
Call Pattern of the Recursive
fib Method
File
FibTrace.java
01: import javax.swing.JOptionPane;
02:
03: /**
04: This program prints trace messages that show how often the
05: recursive method for computing Fibonacci numbers calls itself.
06: */
07: public class FibTrace
08: {
09: public static void main(String[] args)
10: {
11:
String input = JOptionPane.showInputDialog("Enter n: ");
12:
int n = Integer.parseInt(input);
13:
14:
int f = fib(n);
15:
16:
System.out.println("fib(" + n + ") = " + f);
17:
System.exit(0);
18: }
19:
20: /**
21:
Computes a Fibonacci number.
22:
@param n an integer
23:
@return the nth Fibonacci number
24: */
25: public static int fib(int n)
26: {
27:
System.out.println("Entering fib: n = " + n);
28:
int f;
29:
if (n <= 2) f = 1;
30:
else f = fib(n - 1) + fib(n - 2);
31:
System.out.println("Exiting fib: n = " + n
32:
+ " return value = " + f);
33:
return f;
34: }
35: }
File FibLoop.java
01: import javax.swing.JOptionPane;
02:
03: /**
04: This program computes Fibonacci numbers using an iterative
05: method.
06: */
07: public class FibLoop
08: {
09: public static void main(String[] args)
10: {
11:
String input = JOptionPane.showInputDialog("Enter n: ");
12:
int n = Integer.parseInt(input);
13:
14:
for (int i = 1; i <= n; i++)
15:
{
16:
double f = fib(i);
17:
System.out.println("fib(" + i + ") = " + f);
18:
}
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:
33:
34:
35:
36:
37:
System.exit(0);
}
/**
Computes a Fibonacci number.
@param n an integer
@return the nth Fibonacci number
*/
public static double fib(int n)
{
if (n <= 2) return 1;
double fold = 1;
double fold2 = 1;
double fnew = 1;
for (int i = 3; i <= n; i++)
{
fnew = fold + fold2;
fold2 = fold;
fold = fnew;
38:
}
39:
return fnew;
40: }
41: }