find output of a recursive function by hands

[karlemange]

int f(int x, int y) {
if(x < 0 || y < 0)
return x - y;
else 
return f(x - 1, y) + f(x, y -1);

if i want to calculate the output of f(2,1) by hand, how should i do it?

i started with this: f(2,1) -> return f(1,1) + f(2,0)
then f(1,1) -> return f(0,1) + f(1,0)
then f(0,1) -> return f(-1,1) + f(0,0) (from f(-1,1) return -2)
then f(0,0) -> return f(-1,0) + f(0,-1) (from f(-1,0) return -1; from (0,-1) return 1)

i do the same with f(2,1), f(1,0), etc. but i come up with an answer different from my compiler's answer (it gives 5).

what should be the correct steps to find the value?

thanks!

[lastchance]

Your compiler is correct.

You can shortcut some of the calculations. Because of the symmetry in the immediate expansion, but the antisymmetry in x-y, the end recursion of
f(n,n) is 0.

Also,
f(n,0) = f(n-1,0) + (n+1), a simpler recursion.

Then
f(2,1) = f(1,1) + f(2,0)
= 0 + f(1,0) + 3 using the results above
= 0 + f(0,0) + 2 + 3
= 0 + 0 + 2 + 3
=5

[karlemange]

oh! thanks!!! that's much clearer to me!!