Segmentation fault in C recursive Combination (nCr)

Question

PLease help me out here. The program is supposed to recursively find out the combination of two numbers. nCr = n!/ (r!(n-r)! ). I'm getting this error message when i compile it on GCC.

Here's what the terminal shows:

Enter two numbers: 8 4 Segmentation fault

---

(Program exited with code:139)

The code is given here:

    #include<stdio.h>

float nCr(float, float, float);

int main()
{

 float a, b, c;
 printf("Enter two numbers: \n");
 scanf("%f%f", &a, &b);
 c = nCr(a, b, a-b);
 printf("\n%.3f", c);
 return 0;
}

float nCr(float n, float r, float p)
{

        if(n<1)
 return (1/(p*r))*(nCr(1, r-1, p-1));

 if(r<1)
 return (n/(p*1))*(nCr(n-1, 1, p-1));

 if(p<1)
 return (n/r)*(nCr(n-1, r-1, 1));

 return ( n/(p*r) )*nCr(n-1, r-1, p-1);
}

Answer 1

Have you tried debugging the crash? You can use this page as a reference. If you can post information about the crash (stack trace, etc.) that would help both yourself and the SO community in figuring out the problem.

Answer 2

Since nCr doesn't have any return statement that is not recursive, it will recurse infinitely. Since this will cause the stack to grow infinitely, you get your segmentation fault.

Basically a recursive function should always have at least one possible path through the function which does not recurse. Otherwise you have infinite recursion.

Answer 3

You surely fall into infinite recursion to get this Segmentation Fault. You essentially don't have base case to stop the recursion as sepp2k mentioned.

Answer 4

1. Why are you using floats? Combinations only deal with integers... Use a formula that doesn't involve floating point arithmetic.
2. No matter what happens, a recursive call is being made. This means that you will have infinite recursion. This is why the segmentation fault happens. I suggest you read the link I gave you and implement your program using one of the formulas given there. Pay attention to the base cases.

Answer 5

Thanks everyone for the suggestions. It works, it works! :)

    #include<stdio.h>

    float comb(float, float);

int main()
{

    float a, b, c;
    printf("Enter two numbers: \n");
    scanf("%f%f", &a, &b);
    printf("\n%.0f", comb(a, b) );
    return 0;
}

float comb(float n, float k)
{

    if(k==1)
        return n;


    return (n/k)*comb(n-1, k-1); 

}

Please note, though combination works for integers taking int value here will produce error due to the n/k division. Hence the usage float. Without %.0f we'd still get 6 zeroes after the point.