java - Binomial Coefficients. Recursion tree. How to avoid calculating same values multiple times -

i working program called binomialcoefficients.

i did box trace on c(5,3) , returns 10 correct, noticed in full recursion tree c(5, 3), value c(3, 2) evaluated 2 times, , c(2, 1) evaluated 3 times.

what modification avoids computing same values multiple times?

here function show context.

public static int c(int n, int k) {    if(k>n)       return 0;    else if(k==0 || k==n)       return 1;    else       return c(n-1, k-1)+c(n-1, k);   } 

one modification use multiplicative formula. you'd have consider integer overflow.... (edit: have @ @ajb said in comment)

i'd suggest using map caching result:

map<string, integer> cache = new hashmap<>();      public static int c(int n, int k) {   string cachekey=key(n,k);   if (cache.containskey(cachekey){     return cache.get(cachekey);   if(k>n)     return 0;   else if(k==0 || k==n)     return 1;   else {     int result = c(n-1, k-1)+c(n-1, k);     cache.put(cachekey, result);     return result ; }  public string key(int n, int k){   return n +"_"+k; } 

of course using strings keys not efficient way, i'd guess it's still way faster recalculating same value on , on again.