CODEWITHSUNDEEP
c
Bogdan Praščević
Bogdan Praščević

Reputation: 21

C code for binomial coefficents

I have written code in C which calculates binomial coefficients and adding them in double array. I tested the function with printing (printf) coefficients and it is working, but when I try to put coefficients into double array (matrix), it just froze and I need to stop compiling (it doesn't show any error).

Code for this is:

#include <stdio.h>
#include <math.h>

int binomialCoeff(int n, int k) {
    int p;
    // Base Cases
    if (k == 0 || k == n)
        return 1;
    p = binomialCoeff(n - 1, k - 1) + binomialCoeff(n - 1, k);
    return  p;
}

/* Driver program to test above function*/
int main() {
    int r = 5, l, j;
    int c[100][100];
    for (j = 2; j < r + 1; j++)
        for (l = 0; l < r + 1; l++) {
            c[j][l] = binomialCoeff(j, l);
            printf("   c=%d", c[j][l]);
        }
    return 0;
}

Any suggestion on what is happening with my code?

Upvotes: 2

Views: 470

Answers (3)

anoopknr
anoopknr

Reputation: 3355

This is mistake with your function binomialCoeff() .

  1. Your function do not check the condition n should be n>=k in binomial coefficients.So your recursive function call goes infinite and cause segmentation error .

Try this modified code , This will work ;-

int binomialCoeff(int n, int k)
{
    int p;
    if(n < k) // new condition
        return 0;
    // Base Cases
    if (k == 0 || k == n)  
        return 1;
    p = binomialCoeff(n - 1, k - 1) + binomialCoeff(n - 1, k);
    return p;
}

Output :-

  c=1   c=2   c=1   c=1   c=1   c=1   c=1   c=3   c=3   c=1   c=1   c=1   c=1   c=4   c=6   c=4   c=1   c=1   c=1   c=5   c=10   c=10   c=5   c=1

Upvotes: 1

chqrlie
chqrlie

Reputation: 144740

You call your binomialCoeff function with arguments outside its definition domain: it does not handle cases where k > n. It is safer to define it more strictly:

#include <stdio.h>
#include <stdlib.h>

int binomialCoeff(int n, int k) {
    // Base Cases
    if (n < 0 || k < 0 || k > n)
        return 0;
    if (k == 0 || k == n)
        return 1;
    return binomialCoeff(n - 1, k - 1) + binomialCoeff(n - 1, k);
}

/* Driver program to test above function*/
int main(int argc, char *argv[]) {
    int r, l, j;
    int c[100][100];

    if (argc > 1) {
        r = atoi(argv[1]);
        if (r >= 100)
            return 1;
    } else {
        r = 5;
    }
    for (j = 0; j <= r; j++) {
        for (l = 0; l <= j; l++) {
            c[j][l] = binomialCoeff(j, l);
            printf(" %7.0d", c[j][l]);
        }
        printf("\n");
    }
    return 0;
}

Note however that this recursive method is extremely slow for moderately large argument values (try 32). Since you are storing the binomial coefficients, you should compute them iteratively, as you would by hand:

#include <stdio.h>
#include <stdlib.h>

/* Simpler program to compute and print the binomial coefficients */
int main(int argc, char *argv[]) {
    int r, l, j;
    int c[100][100];

    if (argc > 1) {
        r = atoi(argv[1]);
        if (r >= 100)
            return 1;
    } else {
        r = 5;
    }
    c[0][0] = 1;
    for (j = 1; j <= r; j++) {
        c[j][0] = 1;
        for (l = 1; l < j; l++) {
            c[j][l] = c[j - 1][l - 1] + c[j - 1][l];
        }
        c[j][j] = 1;
    }
    for (j = 0; j <= r; j++) {
        for (l = 0; l <= j; l++) {
            printf(" %7.0d", c[j][l]);
        }
        printf("\n");
    }
    return 0;
}

Upvotes: 1

Nicholas Pipitone
Nicholas Pipitone

Reputation: 4142

You're running into a problem when j=2 and l=3.

Calculating binomialCoeff(2, 3) requires knowledge of binomialCoeff(1, 3)

Calculating binomialCoeff(1, 3) requires knowledge of binomialCoeff(0, 3)

Calculating binomialCoeff(0, 3) requires knowledge of binomialCoeff(-1, 3)

Calculating binomialCoeff(-1, 3) requires knowledge of binomialCoeff(-2, 3)

...

See how this will take infinitely long? Try changing it to for( l = 0; l < j; l++ ) to see it not freeze. To fix the bug, try to prevent binomialCoeff(0, 3) from calling binomialCoeff(-1, 3)

As a side note...

Posting this means that you aren't using a debugger, and coding without a debugger means you'll be posting on stackoverflow every couple minutes (As you know, coding => bugs). If you had a debugger, you could follow the loop and then realize when you get sucked down the binomialCoeff(-100, 3) path. Use Visual Studio or gdb (The former is much better for people who are new to programming). If you're not on Windows then CodeBlocks works equally well. Eventually you'll be able to look at code and see what base cases you need, but debuggers develop that intuition.

(Coninuing to post on stackoverflow without debugging might get you into trouble)

Upvotes: 0

Related Questions