Binomial coefficient recursive solution in C

Question

Why is my solution to binomial coefficient crashing? I've really tried to learn recursion, but I still think I am not clear about about it. I wonder if anyone can help me learn about recursion, and how to think recursively?

Even when I write a good base case, my program crashes. Any link to learn recursion with clear demonstration would be very helpful for me.

Here is my code for binomial coefficient, and I'm unable to find the bug/error, looking for your help.

code:

#include<stdio.h>   

long long m,n,o,p,result;  

long long binomial(long long  n,long long m)
{
   if(n==m)
       return 1;
   else {
       if(m==0)
           return 1;
       else {
           o=binomial(n-1,m);
           p=binomial(n-1,m-1);
           return o+p;
       }
   }
}

int main()
{
    printf("Please Enter The Value Of n:\n");
    scanf("%lld",&n);

    printf("Now Enter The value of m:\n");    
    scanf("%lld",&m);

    result = binomial(n,m);
    printf("Resultant Binomial coefficient: %lld\n",result);
    return 0;
}

Answer 1

The binomial coefficient is only defined for pairs n and k when n >= k. It is conventional to use n and k in binomial coefficient expressions, but these correspond to n and m in your code.

You need to include some error-checking of input to avoid problems. Your code crashes when n is less than m because each time the statement o=binomial(n-1,m); is executed, the value of n in the called function is reduced, but n is already smaller than m, which is nonzero (if m were zero the function would have simply returned 1), so n == m can never occur.

Incidentally, you can improve your code in a few ways. Using global variables is generally a bad idea, and it would be better to move the declaration:

long long m, n, result;

into main(), where these variables are needed. Also, the function signature for main() should be int main(void). And you can tighten up the logic in the binomial() function considerably, removing the need for o and p:

long long binomial(long long  n,long long m)
{
    if (m != 0 && n != m) {
        return binomial(n-1, m) + binomial(n-1, m-1);
    } else {
        return 1;
    }
}