Lesson: Recursion
Motivation: Use the Fibonacci method to illustrate three ways, two of them recursive, to generate terms in the sequence
The Fibonacci sequence starts out with two 1s then each successive number is the sum of the previous two numbers. Here are the first few terms in the sequence:
1 1 2 3 5 8 13 21 34 55 89 . . .
A simple but very inefficient recursive solution
public static int fib(int n)
{
if (n <= 2) return 1;
else return fib(n - 1) + fib(n - 2);
}
A simple and efficient iterative solution
public static double fib(int n)
{
if (n <= 2) return 1;
double prev = 1;
double curr = 1;
double next = 1;
for (int i = 3; i <= n; i++)
{
next = prev + curr;
prev = curr;
curr = next;
}
return curr;
}
An efficient recursive solution
public static int fibrec(int prev, int curr, int count, int n){
if (n <= 2) return 1;
if (count == n) return curr;
else return fibrec(curr, prev+curr, count+1, n);
}
Motivation: Use recursion to generate permutations of a string recursively. For example, permutations of abc are abc, acb, bac, bca, cab, cba. For a string of length n there are n! distinct permutations.
A Recursive Strategy
For each letter L in the string
Put L in the first position of the result string
Form the “tail” string by removing L from the original string
Recursively permute the tail string and attach the result to the letter L
The PermutationGenerator constructor
public PermutationGenerator(String aWord)
{
word = aWord;
current = 0;
if (word.length() > 1)
tailGenerator = new PermutationGenerator(word.substring(1));
}
Checking if more permutations are possible
public boolean hasMorePermutations()
{
// is there another letter that can be selected
return current < word.length();
}
Developing the next permutation recursively
public String nextPermutation()
{
if (word.length() == 1) // this is the base case, only one letter
{
current++;
return word;
}
String r = word.charAt(current) + tailGenerator.nextPermutation();
if (!tailGenerator.hasMorePermutations())
{
current++;
if (current < word.length())
{
// form the tail string by removing the selected character
String tailString = word.substring(0, current)
+ word.substring(current + 1);
tailGenerator = new PermutationGenerator(tailString);
}
}
return r;
}
Motivation: Use recursive descent parsing to evaluate arithmetic expressions containing integers, parentheses, and the operations +, -, *, / . Here is an example of program operation:
2+3=5
2+3*4=14
(2+3)*4=20
5-1-1-1=2
5-1-(1-1)=4
(2*3+4*5)/6=4
A Recursive Grammar for Expressions as a BNF
<expr> <term> | <expr> + <term> | <expr> - <term>
<term> <factor> | <term> * <factor> | <term> / <factor>
<factor> <integer> | ( <expr> )
<integer> <digit> | <integer> <digit>
<digit> 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
A Recursive Grammar for Expressions as an EBNF
<expr> <term> { ( + | - ) <term> }
<term> <factor> { ( * | / ) <factor> }
<factor> <integer> | ( <expr> )
<integer> <digit> { <digit> }
<digit> 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
Motivation for Tokenizing the String input:
The input stream is split into tokens of two types:
- Single characters such as +, -, *, /, ( and )
- A sequence of adjacent digits, such as 1234
For the recursive descent parser to work properly we need two tokenizer methods:
- nextToken() returns the next token and moves forward in the string
- peekToken() returns the next token but does not advance in the string
The ExpressionTokenizer constructor
public ExpressionTokenizer(String anInput) {
input = anInput;
start = 0;
end = 0;
nextToken();
}
The peekToken method
public String peekToken() {
if (start >= input.length()) return null;
else return input.substring(start, end);
}
The nextToken method
public String nextToken() {
String r = peekToken();
// now peek ahead for the next token
start = end;
if (start >= input.length()) return r;
if (Character.isDigit(input.charAt(start)))
{
end = start + 1;
while (end < input.length() & Character.isDigit(input.charAt(end)))
end++;
}
else
end = start + 1;
return r;
}
The getExpressionValue method: <expr> <term> { ( + | - ) <term> }
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;
}
The getTermValue method: <term> <factor> { ( * | / ) <factor> }
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;
}
return value;
}
The getFactorValue method: <factor> <integer> | ( <expr> )
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());
return value;
}