title: Which is better way to calculate nCr
body: <p>Approach 1:<br>
  C(n,r) = n!/(n-r)!r!</p>
  
  <p>Approach 2:<br>
  In the book <a href="http://www.google.com/url?sa=t&amp;rct=j&amp;q=&amp;esrc=s&amp;source=web&amp;cd=1&amp;ved=0CF0QFjAA&amp;url=http://www.math.upenn.edu/~wilf/website/CombinatorialAlgorithms.pdf&amp;ei=aTcdUJiDHojsrAfAn4C4Aw&amp;usg=AFQjCNGgowD1UYCUKKvzibbMHWzfnSGSBQ&amp;sig2=SA2ePQJ-b-0FRkz1RnlGVA">Combinatorial Algorithms by wilf</a>, i have found this:<br>
  C(n,r) can be written as <code>C(n-1,r) + C(n-1,r-1)</code>.</p>
  
  <p>e.g.     </p>
  
  <pre><code>C(7,4) = C(6,4) + C(6,3) 
         = C(5,4) + C(5,3) + C(5,3) + C(5,2)
         .   .
         .   .
         .   .
         .   .
         After solving
         = C(4,4) + C(4,1) + 3*C(3,3) + 3*C(3,1) + 6*C(2,1) + 6*C(2,2)
  </code></pre>
  
  <p>As you can see, the final solution doesn't need any multiplication. In every form C(n,r), either n==r or r==1.</p>
  
  <p>Here is the sample code i have implemented:</p>
  
  <pre><code>int foo(int n,int r)
  {
       if(n==r) return 1;
       if(r==1) return n;
       return foo(n-1,r) + foo(n-1,r-1);
  }
  </code></pre>
  
  <p>See <a href="http://ideone.com/KIUbg">output</a> here.</p>
  
  <p>In the approach 2, there are overlapping sub-problems where we are calling recursion to solve the same sub-problems again. We can avoid it by using <a href="http://en.wikipedia.org/wiki/Dynamic_programming">Dynamic Programming</a>.</p>
  
  <p>I want to know which is the better way to calculate C(n,r)?. </p>