CareerCup

Two ways come to my mind:
1) Memoization. Use caching to prevent recalculations. Every time you need to calculate F(m,n) first checki in cache if the answer exists. Then you won't recalculate. If the answer is not available, calculate it and then store in cache. SO you will avoid exponential growth by guaranteing that no calculation for m,n is performed twise. The obvious disadvantage is memory usage which can be as much as O(xy).
2. The second (much better) solution is to use recurrent statement in the conditions above, to derive a simple formula for immediately returning a solution without any recursive calls. As far as I can see (using simple 2D coordinates), if m>=n F(m,n) = (n+1) * n - n - 1; if m < n F(m,n) = (m+1) * m - m - 1 + (n - m);

i think this equation represents a 2-d array whose each element is sum of 2 elements i.e
1. immediate above element(previous row's element with same column index).
2. element before 1st element (previous row, column index -1).

for base cases all elements in first row, first column is one.

so you can freely use 2 for loops, to evaluate values and there will be no worry of stack usage.

Looks like the recursion for binomial coefficient.

Use a 2d map to memorize previous calculations. Once calculation reaches row m, there is no need to keep row m-2 and above in map. Similarly, no need to keep column n-2 and before in map. So the map only goes to 2*m+2*n elements. No memory overflow.

Implementation is Scala

var map = Map[(Int, Int),Long]()
  
  def F(m:Int, n:Int):Long = {
    (m,n) match {
      case (1,_) =>1
      case (_,1) =>1
      case _ =>
        if (!map.contains((m,n))) {
	        val f1 = F(m-1, n-1)
	        val f2 = F(m, n-1)
	      	map = map.updated((m,n), f1+f2)
	      	//no need to store m-2 row and n-2 column
	      	//remove to save space
	      	map.dropWhile( t=> t._1._1<m-1 && t._1._2<n-1)
        }
        map(m,n)
    } 
  }

awesome trick is matrix exponentiation...:)

check out - zobayer.blogspot.com/2010/11/matrix-exponentiation.html

if (m>0 and n>0)
if m=1
return 1
else
return 2^(n-1)