Java Reference
In-Depth Information
public class Test {
public static void main(String args [])
{
long sum = 0L ;
for ( int i=1;i < = 64; i++) {
sum = sum + f ( i ) ;
System. out . println (sum) ;
}
public static long f( int day) {
if (day==1)
return 1L;
if (day==2)
return 1L;
return f(day
1)+f (day
2) ;
}
}
The f method calculates how much grain the king owes for that day. The main method
calculates and prints the total amount of grain that the king will owe if he happens to lose.
Let us closely examine the f method. The first two if statements are the base cases .If
it is day one or day two, then the king knows exactly how much he needs to pay. Otherwise,
he needs to pay the sum of the grain for the previous two days. The recursive formula: f(x)
= f(x-1)+f(x-2) is our general case .
When writing a recursive method (i.e., a method that calls itself), always start
with the base case or the base cases. These are the simple cases where you know the
solution. Next, write the general case. This is where you break a complex problem
into simpler problems. The general case is where the recursive call is made.
In the above code, the king has no idea what the exact value of f(30) is. However, he
knows that, if by some kind of magic, he finds the value of f(29) and f(28) , then the value
of f(30) will be simply the sum of the two numbers. This is the general idea of a recursive
method. We do not know how to directly solve the general problem. However, we know how
to break it down into smaller problems. A recursive program must always start with the
base cases. If it does not, then we will always simplify the problem into simpler problems
and the process will never terminate. The base cases insure that when the problem is simple
enough, we can provide a direct solution and stop the recursion.
Accidentally, the f method computes the Fibonacci number. Figure 14.1 shows how the
method computes the fifth Fibonacci number. The value of f(5) is computed as f(4)+f(3) .
The value of f(4) is recursively computed as f(3)+f(2) and so on.
When a base case is reached, that is f(2) or f(1) , our program provides a direct solution
to the problem. Note that from Figure 14.1 we can determine that the algorithm is not very
ecient. The reason is that, for example, the value of f(3) is computed twice.

Search WWH ::

Custom Search