Example for the analysis of a recursive function

l is a matrix of size [1...n, 1...n]

function: rec(i,j)
  if (i*j == 0)
    return 1
  else
    if (l[i,j] == 0)
      l[i,j] = 1 * rec(i-1,j) + 2 * rec(i,j-1) + 3 * rec(i-1,j-1)
    return l[i,j]
end_function

for i=1 to n
  for j=1 to n
    l[i,j] = 0

rec(n,n)

The nested for's are O(n2). But i have difficulties to analyse the recursive part. There is another variation of this example with l as 3d. And the essential part of 3drec function is defined as:

if (l[i,j,k] == 0)
  l[i,j,k] = 2 * rec(i-1,j,k) + 2 * rec(i,j-1,k) + 2 * rec(i,j,k-1)

Anyway let's think about the 2d version again. I thought something like that (that's the running time for the whole code including the nested loops):

T(n) = T(n-1, n2) + T(n, n-12) + T(n-12, n-12)

And i'm stuck here. Besides i don't know if i did right till this point.

Here's the correct recurrence for the running time of rec:
$$
f(i,j) = \begin{cases} O(1), & i = 0 \text{ or } j = 0, \\
f(i-1,j) + f(i,j-1) + f(i-1,j-1) + O(1), & \text{otherwise}. \end{cases}
$$
The running time of the entire program is $f(n,n) + O(n^2)$. Now it remains to solve the recurrence for $f$, which I leave to you.

StackExchange Computer Science Q#9162, answer score: 6