Java Reference
In-Depth Information
/
**
Recursivelygenerateandreturnthen'thFibonacci
number
*
/
staticlongfibr(intn){
//fibr(91)isthelargestvaluethatfitsinalong
assert(n>0)&&(n<=91):"noutofrange";
if((n==1)||(n==2))return1; //Basecase
returnfibr(n-1)+fibr(n-2); //Recursivecall
}
This algorithm turns out to be very slow, calling
Fibr
a total of Fib(n) times.
Contrast this with the following iterative algorithm:
/
**
Iterativelygenerateandreturnthen'thFibonacci
number
*
/
staticlongfibi(intn){
//fibr(91)isthelargestvaluethatfitsinalong
assert(n>0)&&(n<=91):"noutofrange";
longcurr,prev,past;
if((n==1)||(n==2))return1;
curr=prev=1; //currholdscurrentFibvalue
for(inti=3;i<=n;i++){//Computenextvalue
past=prev; //pastholdsfibi(i-2)
prev=curr; //prevholdsfibi(i-1)
curr=past+prev; //currnowholdsfibi(i)
}
returncurr;
}
Function
Fibi
executes the
for
loop n 2 times.
(a) Which version is easier to understand? Why?
(b) Explain why
Fibr
is so much slower than
Fibi
.
2.12 Write a recursive function to solve a generalization of the Towers of Hanoi
problem where each ring may begin on any pole so long as no ring sits on
top of a smaller ring.
2.13 Revise the recursive implementation for Towers of Hanoi from Section 2.5
to return the list of moves needed to solve the problem.
2.14 Consider the following function:
staticvoidfoo(doubleval){
if(val!=0.0)
foo(val/2.0);
}
This function makes progress towards the base case on every recursive call.
In theory (that is, if
double
variables acted like true real numbers), would
this function ever terminate for input
val
a nonzero number? In practice (an
actual computer implementation), will it terminate?
2.15 Write a function to print all of the permutations for the elements of an array
containing n distinct integer values.
