Laboratory 5 Solutions

CSCI 132 Data Structures--Spring 2014

Laboratory 5 Solutions

For n = 46, fibRec takes about 20 secs, but fibTail and fibWhile take less than 1 sec.

Solution to fibRec.cc code:

/*******************************************************************
 * Name: Brenda Student
 * Date: 3/12/14
 * Course: CSCI 132 Section 01
 * Assignment: Lab 5
 * Instructor: Royden
 * Program: fibRec.cc
 * Purpose: A program that calls a recursive function to compute the nth
 *          fibonacci number.
 ***************************************************************************/
#include <iostream>

using namespace std;

int fibRec(int);

int main(void) {
  int num;		//number for computing fibonacci function
  cout << "Enter an integer: ";
  cin >> num;

  cout << "The fibonacci number for month " << num << " is "
       << fibRec(num) << endl;

}

/*Recursively compute fibonacci number*/
int fibRec(int n) {
  if (n < 2) {
    return n;
  } else {
    return fibRec(n-1) + fibRec(n-2);
  }
}

Solution to fibTail.cc code:

/*******************************************************************
 * Name: Brenda Student
 * Date: 3/12/14
 * Course: CSCI 132 Section 01
 * Assignment: Lab 5
 * Instructor: Royden
 * Program: fibTail.cc
 * Purpose: A program that calls a tail recursive function to compute the nth
 *          fibonacci number.
 ***************************************************************************/
#include <iostream>

using namespace std;

int fibIter(int);
int fibTail(int, int, int, int);

int main(void) {
  int num;	//number for computing fibonacci function
  cout << "Enter an integer: ";
  cin >> num;

  cout << "The fibonacci number for month " << num << " is "
       << fibIter(num) << endl;

}

int fibIter(int n) {
  return fibTail(n, 1, 0, 1);
}

/*Use tail recursion to compute fibonacci number*/
int fibTail(int n, int i, int fib_i_minus1, int fib_i) {
  if (n == i) {
    return fib_i;
  } else {
    return fibTail(n, i+1, fib_i, fib_i + fib_i_minus1);
  }
}

Solution to fibWhile.cc code:

/*******************************************************************
 * Name: Brenda Student
 * Date: 3/12/14
 * Course: CSCI 132 Section 01
 * Assignment: Lab 5
 * Instructor: Royden
 * Program: fibwhile.cc
 * Purpose: A program that calls a function to compute the nth
 *          fibonacci number using a while loop
 ***************************************************************************/
#include <iostream>

using namespace std;

int fibWhile(int);

int main(void) {
  int num;		//number for computing fibonacci function
  cout << "Enter an integer: ";
  cin >> num;

  cout << "The fibonacci number for month " << num << " is "
       << fibWhile(num) << endl;

}

/*Compute Fibonacci number with a while loop*/
int fibWhile(int n) {
  int i= 1;
  int fib_i_minus1 = 0;
  int fib_i = 1;
  while (i < n) {
    int fib_inext = fib_i + fib_i_minus1;
    fib_i_minus1 = fib_i;
    fib_i = fib_inext;
    i = i+1;
  }
  return fib_i;
}