Lab 6 Solution

(4 pts) Iteration vs. Recursion

You will practice writing and timing iterative and recursive versions of the same function. You will use the following code to time both versions of your solution to the Fibonacci problem described below.

#include <iostream>

#include <sys/time.h>

#include <cstdlib>

using std::cout;

using std::endl;

int main() {

typedef struct timeval time;

time stop, start;

gettimeofday(&start, NULL);

//Time your iterative or recursive function here.

gettimeofday(&stop, NULL);

if(stop.tv_sec > start.tv_sec)

cout << "Seconds: " << stop.tv_sec-start.tv_sec << endl;

else

cout << "Micro: " << stop.tv_usec-start.tv_usec << endl;

return 0;

}

First, you will write a function called, ​fib_iter(),​that has one parameter, n, of type int,
​




​​
​​

and returns the nth Fibonacci number, Fn. The Fibonacci numbers start with F0 is 0, F1
​​
​​
​​
​​
​​


is 1, F2 is 1, F3 is 2, F4 is 3, F5 is 5, F6 is 8, etc...





Formally stated:
F​    = F​ + F​    for i = 2, 3, …; where F​ = 0 and F​ = 1
i+2 ​    i ​    i+1 ​    0​    1 ​

Your iterative version of the function should use a loop to compute each Fibonacci number, discarding numbers along the way, until you reach your desired number.

Next, you will write a recursive version of the function called, ​fib_recurs(),​that also takes one parameter, n, of type int, and returns the nth Fibonacci number, F​.
n​

Using the code supplied above, ​time the iterative and recursive solutions for finding the 1​st​, 5​th​, 15​th​, 25​th​, and 45​th​Fibonacci numbers​. Determine how long each function

takes, and compare and comment on your results.

Show your TA a trace through the recursive solution for n=5. Additionally, produce a table of times for n = 1, 5, 15, 25, and 45 for each version of the function.

(6 pts) Fibonacci Application

Design and implement your solution for the following problem.

You're standing at the base of a staircase and would like to get to the top. A small stride will take you up one step while a large stride takes you up two steps. You would like to count the number of possible ways you could climb the entire staircase based on different combinations of large and small strides.

For example, a staircase with three steps can be climbed in three different ways:

    • three small strides

    • one small stride followed by one large stride

    • one large followed by one small stride

How could you apply the Fibonacci number series to this problem? What are the base cases for counting the ways you can climb stairs by going one stair or two stairs at a time? How many different ways can you climb 4 stairs? 5 stairs?