Task 1Efficient Computation of Fibonacci Numbers

The Fibonacci sequence is a well-known mathematical sequence in which each term is the sum of the two previous terms. The sequence can be defined as follows:

fib(0) = 0

fib(1) = 1

fib(n) = fib(n-1) + fib(n-2) n>1

Write a recursive method to determine the nth number in the sequence. Put the method in a class called Fib. Note the method should be static. Think why.

File TestFib.java contains the tester. Save this file to your directory. Use it to test your recursive method.

To trace the recursive calling path, add a print statement at the beginning of your fib method that indicates the current parameter, e.g., Now control is in fib (3) if the parameter is 3. Before you run the program, try to estimate the message sequence based on your understanding of recursion. This is easiest if you first draw the call tree on paper.

Now run the program and examine if the output messages are same as your estimation. Figure out the reason if they are not same a very good chance to completely understand recursion. Ask the instructor or TA to explain if needed.

Task 2Counting and Summing Digits

Download DigitPlay.java. In class we examined the recursive method that counts the number of digits in a positive integer. Complete the numDigits method which does the same thing as the in-class example and run the program. Try several numbers with different length. For example, input 3278 will generate output 4; 32780 should generate output 5. Also try a negative number. Is the output reasonable?

Now add another method sumDigits, which sums those digits in the input positive integer. For example, input 321 will generate output 6 since 3+2+1 = 6. Define this method in the recursive way too. You can modify numDigits easily to get sumDigits!

Be reminded that sumDigits should be static too, so it can be invoked directly in the main method without creating an object. Add code to main() to test your method