Recursive Bionomial Coefficient in C

I have to find a recursive function in C to compute big Binomial Coefficients. e.g. 59C10
I’ve written the below code but takes too much time. Is there a better way to do it ?

long long nCk(long long n, long long k)
{
if(n == k || k == 0)
{
    return 1;
}
else if(k == 1)
{
    return n;
}
else
{
    return nCk(n-1,k-1) + nCk(n-1,k);
}
}

>Solution :

First of all, I don’t think recursion is necessarily the right way to do this.

However, you can make the calculation take less than a second if you use memoization, like Eric Postpischil suggested.

The program below uses a naive and unnecessarily large cache to calculate 59C10. It outputs 62828356305, which seems to be correct:

#include <stdio.h>
#include <stdint.h>

uint64_t cache[60][60];

uint64_t nCk(uint64_t n, uint64_t k)
{
  if (k > n)
  {
    return 0;
  }
  else if (k == n || k == 0)
  {
    return 1;
  }
  else if (cache[n][k])
  {
    return cache[n][k];
  }
  else
  {
    return cache[n][k] = nCk(n-1, k-1) + nCk(n-1, k);
  }
}

int main()
{
  printf("%lld\n", nCk(59, 10));
}

The cache is actually way bigger than it needs to be: if we restructure things, it would only need to hold two rows of the binomial triangle at a time (the previously-computed one and the one we are working on).