Recursive function definition, how does my teacher arrive at this answer?

Question

I am currently revising for my maths exam in school and there is a section on recursion. The question is explained as follows: $$f(m, n) =\begin{cases} n + 1 &\text{if } m = 0\\ f(m − 1, 1) &\text{if } m > 0 \text{ and } n = 0\\ f(m − 1, f(m, n − 1)) &\text{if } m > 0 \text{ and } n > 0\\ \end{cases}$$

calculate:

1) $f(1,1)$

2) $f(1,2)$

My current problem is i don't understand how my teacher arrives at this answer:

$$f(1, 1) = f(0, f(1, 0)) = f(1, 0) + 1 = f(0, 1) + 1 = 1 + 1 + 1 = 3$$

and:

$$f(1, 2) = f(0, f(1, 1)) = f(1, 1) + 1 = 3 + 1 = 4$$

I understand the principle of recursion but I am struggling to execute the above, could somebody work through the example $f(1,1)$ so I can how how it is done?

Answer 1

These are the steps for 1): \begin{align} f(1, 1) &= f(0, f(1, 0)) &\text{by rule 3}\\\\ &= f(0, f(0, 1)) & \text{by rule 2}\\\\ &= f(0, 2) & \text{by rule 1}\\\\ &= 3 & \text{by rule 1} \end{align}

The steps for 2), knowing the value of $f(1, 1)$ are \begin{align} f(1, 2) &= f(0, f(1, 1)) & \text{by rule 3}\\\\ &= f(0, 3) & \text{by the above}\\\\ &= 4 &\text{by rule 1} \end{align}

Answer 2

rule 1: if $m=0$ then $f\left(m,n\right)=n+1$

rule 2: if $m>0$ and $n=0$ then $f\left(m,n\right)=f\left(m-1,1\right)$

rule 3: if $m>0$ and $n>0$ then $f\left(m,n\right)=f\left(m-1,f\left(m,n-1\right)\right)$

To find is $f\left(1,1\right)$ and here $m=n=1$ so we start by applying the third rule:

$f\left(1,1\right)=f\left(m-1,f\left(m,n-1\right)\right)=f\left(0,f\left(1,0\right)\right)$

Looking at $f\left(1,0\right)$ the second rule tells us to replace it by $f\left(0,1\right)$ resulting in:

$f\left(1,1\right)=f\left(0,f\left(0,1\right)\right)$

Looking at $f\left(0,1\right)$ the first rule tells us to replace it by $2$ resulting in:

$f\left(1,1\right)=f\left(0,2\right)$

Looking at $f\left(0,2\right)$ the first rule tells us to replace it by $3$ resulting in:

$f\left(1,1\right)=3$