CODEWITHSUNDEEP
c++functionloopsrecursion
tjames68w
tjames68w

Reputation: 401

c++ iterative combination function not working

I have a homework problem asking to write an iterative and recursive combination function. place them in a given program to see which takes longer.

I am having a problem with the iterative function. I have gone over it several times and keep getting a mach-o-linker error. I have tried identifying my variables many different ways and still haven't come up with any luck.

any help on this topic would be much appreciated. I think there is a problem with the iterator function or possibly the factorial function, but I am unable to see it for the life of me right now.

thanks again ahead of time

#include <iostream>
#include <sys/time.h>
#include <cstdlib>
using std::cout;
using std::endl;

double iR;
double iN;

typedef unsigned int uint;

uint Factorial(uint n)
  {
  if (n == 0) return 1;
   if (n <= 2) return n;
    else return n * Factorial(n - 1);
  }

  double combination_recursive(double iN, double iR);
  double combination_iterative(int iN, int iR);



  int main(int argc, const char * argv[]) {


typedef struct timeval time;
time stop, start;
gettimeofday(&start, NULL);

iN = 20.0;
iR = 3.0;


  combination_iterative(iN, iR);


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;
}

double comination_iterative(int, int) {

  if (iN == iR) { return 1;}
   if (iR == 0 && iN!= 0) { return 1;}
  else return (iN * Factorial(iN-1))/Factorial(iN-1)*Factorial(iN-iR);

 }

double combination_recursive(double iN, double iR) {
  if (iR < 0 || iR > iN) {
      return 0;
}
  if (iR < 1) {
    return 1;
}
  if (iN == iR) {
    return 1;
}
return combination_recursive(iN - 1, iR) + combination_recursive(iN - 1, iR - 1);
}

Upvotes: 2

Views: 373

Answers (2)

nio
nio

Reputation: 5289

  1. You have a typo in name of your function:

     double comination_iterative(int, int)

    It should be

     double combination_iterative(int, int)

  2. You are missing its forward definition before main function:

     double cobmination_iterative(int, int);

    After fixing this the code compiles.

  3. Next to measure any reasonable times, you shoud call your tested function more times in a 'flat loop'... for example 8 times during one iteration. This way you will avoid error introduced by the time spend just for looping:

      int i;
  for(i=0;i<1000;i++)
  {
     combination_iterative(iN, iR);
     combination_iterative(iN, iR);
     combination_iterative(iN, iR);
     //...
  }

    You should experiment with the number of loop iterations. Here is a question more related to benchmarking.

Upvotes: 0

Paul Renton
Paul Renton

Reputation: 2670

I think your error is due to a simple misspelling.

You make a call to this function in main

combination_iterative(iN, iR);

But you have it defined as

double comination_iterative(int, int) {

if (iN == iR) { return 1;}
 if (iR == 0 && iN!= 0) { return 1;}
  else return (iN * Factorial(iN-1))/Factorial(iN-1)*Factorial(iN-iR);
}

To fix this just change the function definition to match the call

double combination_iterative(int, int) {

if (iN == iR) { return 1;}
 if (iR == 0 && iN!= 0) { return 1;}
  else return (iN * Factorial(iN-1))/Factorial(iN-1)*Factorial(iN-iR);
}

Happy coding and learning C++

Upvotes: 2

Related Questions