2

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);
}
tjames68w
  • 381
  • 1
  • 4
  • 5
  • Welcome to stackoverflow. Can you please trim down your example to the minimum. It will improve the question and increase your chances of a meaningful answer. – Micha Wiedenmann Jul 25 '13 at 19:15
  • 1
    could you please post your errors copypasted from your error console? – nio Jul 25 '13 at 19:15
  • 1
    Watch out: the global variables `iN` and `iR` are not the same as the function parameters `iN` and `iR` in the definition of `combination_recursive`. The definition of `comination_iterative` ignores its parameters entirely and uses the global `iN` and `iR`. – aschepler Jul 25 '13 at 19:24

2 Answers2

2

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++

Paul Renton
  • 2,652
  • 6
  • 25
  • 38
0

  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.

Community
  • 1
  • 1
nio
  • 5,141
  • 2
  • 24
  • 35
  • thank you both nio and paul. the missing definitions came from simply trying different ways to pass my arguments. but the misspelling I completely missed. I feel really silly. I must need glasses... – tjames68w Jul 25 '13 at 19:31
  • Be sure to accept an answer when you feel you have found the best one. – Paul Renton Jul 25 '13 at 20:11