CODEWITHSUNDEEP
c++recursionfactorial
user10430883
user10430883

Reputation:

C++ combination function always resulting 0

can anybody tell me why my Combination function is always resulting 0 ? I also tried to make it calculate the combination without the use of the permutation function but the factorial and still the result is 0;

#include <iostream>
#include <cmath>

using namespace std;

int factorial(int& n)
{
  if (n <= 1)
  {
     return 1;
  }
  else 
  {
    n = n-1;
    return (n+1) * factorial(n);
  }
}
int permutation(int& a, int& b)
{
  int x = a-b;
  return factorial(a) / factorial(x);
}
int Combination(int& a, int& b)
{
   return permutation(a,b) / factorial(b);
}

int main()
{
   int f, s;
   cin >> f >> s;

   cout << permutation(f,s) << endl;
   cout << Combination(f,s);


  return 0;
 }

Upvotes: 1

Views: 187

Answers (2)

Toby Speight
Toby Speight

Reputation: 30888

Your immediate problem is that that you pass a modifiable reference to your function. This means that you have Undefined Behaviour here:

return (n+1) * factorial(n);
//      ^^^             ^^^

because factorial(n) modifies n, and is indeterminately sequenced with (n+1). A similar problem exists in Combination(), where b is modified twice in the same expression:

return permutation(a,b) / factorial(b);
//                  ^^^            ^^^

You will get correct results if you pass n, a and b by value, like this:

int factorial(int n)

Now, factorial() gets its own copy of n, and doesn't affect the n+1 you're multiplying it with.

While we're here, I should point out some other flaws in the code.

  • Avoid using namespace std; - it has traps for the unwary (and even for the wary!).

  • You can write factorial() without modifying n once you pass by value (rather than by reference):

    int factorial(const int n)
{
    if (n <= 1) {
        return 1;
    } else {
        return n * factorial(n-1);
    }
}

  • Consider using iterative code to compute factorial.

  • We should probably be using unsigned int, since the operations are meaningless for negative numbers. You might consider unsigned long or unsigned long long for greater range.

  • Computing one factorial and dividing by another is not only inefficient, it also risks unnecessary overflow (when a is as low as 13, with 32-bit int). Instead, we can multiply just down to the other number:

    unsigned int permutation(const unsigned int a, const unsigned int b)
{
    if (a < b) return 0;

    unsigned int permutations = 1;
    for (unsigned int i = a;  i > a-b;  --i) {
        permutations *= i;
    }

    return permutations;
}

    This works with much higher a, when b is small.

  • We didn't need the <cmath> header for anything.

Suggested fixed code:

unsigned int factorial(const unsigned int n)
{
    unsigned int result = 1;

    for (unsigned int i = 2;  i <= n;  ++i) {
        result *= i;
    }

    return result;
}

unsigned int permutation(const unsigned int a, const unsigned int b)
{
    if (a < b) return 0;

    unsigned int result = 1;
    for (unsigned int i = a;  i > a-b;  --i) {
        result *= i;
    }

    return result;
}

unsigned int combination(const unsigned int a, const unsigned int b)
{
    // C(a, b) == C(a, a - b), but it's faster to compute with small b
    if (b > a - b) {
        return combination(a, a - b);
    }

    return permutation(a,b) / factorial(b);
}

Upvotes: 9

sirh3e
sirh3e

Reputation: 38

You dont calculate with the pointer value you calculate withe the pointer address.

Upvotes: -7

Related Questions