CS1027b Computer Science Fundamentals II

Lab 10

Learning Outcomes

Upon completion of this lab, you should be able to do the following:

General Lab Instructions

IMPORTANT. Submit the .java files that you write for this lab and AnswersLab10.txt through OWL by 11:55pm on Friday, March 27.

Exercise 1: Iterative vs Recursive Algorithms

For some problems it is possible to design natural algorithmic solutions that are recursive and solutions that are iterative. One of these problems is that of computing the n-th Fibonacci number. As you recall the Fibonacci numbers are: 1, 1, 2, 3, 5, 8, 13, 21, ...
The i-th Fibonacci number, for i > 2, is computed by adding the (i-1)-th and the (i-2)-th Fibonacci numbers. An iterative algorithm for this problem uses three variables, say prev, current, and next.
  1. Initially prev stores the first Fibonacci number and current stores the second one.
  2. Then compute the next Fibonacci number by adding the previous tow ones: next = prev + current.
  3. Finally, store in prev and current the last 2 Fibonacci numbers: prev = current and current = next.
  4. Repeat steps 2 and 3 until the n-th Fibonacci number has bee computed.
A recursive algorithm closely follows the following recursive definition of the numbers: Download FibonacciDemo.java from the Sample Code page of the course's website.