segunda-feira, março 05, 2012
2 - Basic Definitions
3 - Series and Summary
4 - Master Method for Recurrences
5 - Converting a Mathematical Definition to a Method
Actually, value-producing recursive algorithms are almost identical to inductive definitions. In fact, creating a value-producing recursive algorithm may require little more than the writing down of the inductive definition.
We can first simply rearrange the parts into an algorithm statement:
Algorithm factorial(n)
if n less than or equal to 1
then the answer is 1
otherwise the answer is: n×factorial(n-1).
It is easy to see that this algorithm is a straightforward piece-by-piece rewriting of the inductive definition: every piece of the algorithm comes directly from the mathematical definition. The Java method for factorial can be derived just as easily from the algorithm:
static int factorial(int n) {
if (n <= 1)
return 1;
else return n * factorial(n - 1);
}
Each component of the definition—and essentially nothing else—appears in the method. It is not uncommon for value-producing recursive algorithms to flow just as directly from the original definition of the needed result. Any mathematical function that can be defined inductively can be similarly translated into a recursive method. This transforms the problem from one of writing methods to solve problems to one of just defining the problem or the mathematical function.
The same approach will work for any inductively defined mathematical functions such as summation:
becomes:
//method for class Calculator
static int sum(int n) {
if (n <= 1)
return 1;
else return n + sum(n - 1);
}
And it gets better: this example extends directly—almost template-like—to any other summation equation. Thus, the sum of squares:
becomes:
static int sumSquares(int n) {
if (n <= 0)
return 0;
else return n*n + sumSquares(n - 1);
}
Source: “Algorithms and Data Structure: The Science of Computing”
0 comments:
Postar um comentário