Fibonacci Recursion
Copy this program and run it in BlueJ.
Then answer the following questions:
/**
* exercise
credited to http://venus.cs.qc.cuny.edu/~waxman/211/fibonacci%20assignment.pdf
* Dr. Jerry Waxman of
Queens College
* Fibonacci program
that needs improvement
* It lists all the fibonacci numbers in the sequence up to the 70th number
*/
public class FibCalc{
public
static int fib(int n){
if(n==1 )
{
return 1;
}
else if (n == 0)
{
return 0;
}
else
{
return fib(n-1) + fib(n-2);
}
}
public
static void main(){
for(int i=1;
i<70; i++)
System.out.println( "fib(" + i+ ") =
" + fib(i));
}
}
1. Why does the program slow down at higher numbers in the
sequence?
2. Draw a picture of the recursive steps for fib(5).
3. Draw a picture of the recursive steps if tail recursion
were used. The formula for tail recursion for fib is:
Where a starts at 1 and b starts at 0, the first two numbers in the sequence.
Instead of this formula:
from :
http://www.codeproject.com/Articles/25470/Recursion-Primer-Using-C-Part-1
4. Code this method of Fibonacci using tail recursion
5. At higher sequences, the fib(i) value gets strange. What is strange about those numbers and why is it happening?
6. Fix the strange numbers.