CSSE 221: Fibonacci, Tail-Recursion and Efficiency

In this exercise, you will learn about recursion and tail-recursion by implementing regular and tail-recursive versions of the fibonacci function. You will explore the difference in running time of the tail-recursive and recursive versions.

1. Create a new Eclipse project and name it Fibonacci.
2. Use Team → Share Project to attach your Fibonacci project to your individual SVN repository for this course.
3. The mathematical function Fibonacci is defined as follows:

Part 1: Standard Fibonacci is inefficient

4. Implement a recursive version of fib which returns the n^th Fibonacci number.
5. Write a main method that runs your method for n = 10, 20, 30, 40, and 50 and prints well-labeled output. Here are the expected answers:
   • fib(10) = 55
   • fib(20) = 6,765
   • fib(30) = 832,040
   • fib(40) = 102,334,155
   • fib(50) = 12,586,269,025
6. Modify your code to count the number of recursive calls used to calculate each value. You'll probably want to use a static field to store the count. Here are some expected answers, though depending on your implementation the number of steps might vary:
   • The 10th Fibonacci number is 55 in 177 steps.
   • The 20th Fibonacci number is 6765 in 21891 steps.
   • The 30th Fibonacci number is 832040 in 2692537 steps.
   • The 40th Fibonacci number is 102334155 in 331160281 steps.
   • The 50th Fibonacci number is 12586269025 in 40730022147 steps.

Part 2: Tail-recusive Fibonacci is much more efficient!

7. Now manually calculate and write down the first ten numbers in the Fibonacci sequence.
8. Implement a tail-recursive version of the fibonacci function which returns the nth Fibonacci number. Keep these hints in mind:
   • In order to develop an algorithm, think about what you did in order to determine the next number in the sequence manually.
   • You will need to create a helper method.
   • You will need to keep track of the prior two numbers in order to determine the next number in the sequence: these become parameters in the helper method.
   • The tail-recursive helper method only calls itself once, which is why it is more efficient.
9. Test your tail-recursive version for n = 10, 20, 30, 40, 50, 100, and 1000.
10. Modify your code to count the number of recursive calls used to calculate each value. You'll probably want to use a static field to store the count. Here are some expected answers, though depending on your implementation, the number of steps might vary:
    • The 10th Fibonacci number is 55 in 10 steps.
    • The 20th Fibonacci number is 6765 in 20 steps.
    • The 30th Fibonacci number is 832040 in 30 steps.
    • The 40th Fibonacci number is 102334155 in 40 steps.
    • The 50th Fibonacci number is 12586269025 in 50 steps.
11. Commit your changes to be graded.