Java Chapter 11 - Recursion
11.1
Divide and Conquer
Recursion is a way to solve a
problem by dividing it into subproblems of the same type (divide and conquer).
It is typically implemented by creating a method that solves a portion of the
problem, then calls itself with the remainder of the problem. For example,
to calculate 8 factorial, you could solve it by multiplying 8 by 7 factorial.
More precisely, x! = x * (x-1)!
Therefore, you could write a method
to calculate x! by returning x * Factorial(x - 1). You could begin writing
the method like this:
int Factorial (int x)
{
return x * Factorial(x - 1);
}
The problem with the preceding code is that it would be an infinite
loop/recursion. Loops (and recursive methods) need a way
to eventually terminate. You can terminate the recursion by returning 1
when x gets to 1:
int Factorial (int x)
{
if (x == 1)
return 1;
// Terminate the
recursion when x gets to 1
else
return x * Factorial(x - 1);
}
The following is a complete recursive factorial program:
thatsthefact.java |
public class thatsthefact |
Output |
8! = 40320 |
Below is another example of recursion. The method counts the number of
dollar signs ( $ ) in a string. This can be done with a for loop by
stepping through each character in the string. It can also be done
recursively by looking at the first letter of the string and calling the method
again with the remainder of the string.
int DollarSigns (String
w)
{
if (w.length()==0) return 0;
// Terminate the
recursion when the length of w is 0
if (w.charAt(0)=='$')
return 1 + DollarSigns(w.substring(1));
else
return DollarSigns(w.substring(1));
}
11.2
Evaluating the Efficiency of Recursion
Recursion is a unique and sometimes simpler method to solve problems.
However, it can sometimes lead to a substantial number of method calls and a
significant amount of CPU time. Therefore, it is often not the most
efficient algorithm to solve a problem. Two ways to evaluate the
efficiency of a recursive program are to count the number of method calls and
the amount of CPU time.
thatsthefact.java |
import java.util.*; |
Output |
20! = 2432902008176640000 |