Lab #4          Due Oct. 23

Lab Objectives

· Demonstrate competence in using recursion and estimating algorithmic efficiency

Lab References

· Chapter 10: Recursion

Problem Description

The Fibonacci numbers are a sequence of numbers that are made in some very specific way. The first and second numbers in the sequence are both 1. The number at position n in the sequence is computed as the sum of the numbers at positions n-1 and n-2. Develop two programs that can print the Fibonacci number at any specified position k (thus k is the input parameter). The first program should do this iteratively and the second program should do this recursively.

Also, produce an estimate of the the efficiency of each of these two algorithms. Explain which one is best and why.