title: Efficiently evaluating a recursive function?
body: <p>I came across with an interesting puzzle on my previous interview.
  You need to implement a function which would fit the following conditions:</p>
  
  <pre><code>m, n - positive integer numbers &gt; 0
  F(m, n) = F(m-1, n-1) + F(m, n-1)
  F(1, n) = 1
  F(m, 1) = 1
  </code></pre>
  
  <p>Obviously you can write the recursive implementation:</p>
  
  <pre><code>int F(int m, int n)
  {
      if(m == 1) return 1;
      if(n == 1) return 1;
      return F(m-1, n-1) + F(m, n-1);
  }
  </code></pre>
  
  <p>But for input data equals one billion it will run very long time because it will get 2^1000000000 iterations :)
  Does anybody have any ideas how to optimize this solution?</p>