Example for the analysis of a recursive function
Here's the correct recurrence for the running time of rec:
$$
f(i,j) = \begin{cases} O(1), &amp; i = 0 \text{ or } j = 0, \\
f(i-1,j) + f(i,j-1) + f(i-1,j-1) + O(1), &amp; \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.