1

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?

Alex Becker
  • 60,569
chris edwards
  • 139

2 Answers2

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}

Arthur
  • 199,419
  • thanks! i got confused at step 3 for f(1,1) i didn't realise if the m part is zero then remove that f component, if that makes sense. – chris edwards Jan 01 '14 at 20:30
  • @chrisedwards From line 1 to 2, and from 2 to 3 on the 1) problem, I'm trying to figure out what the inner $f(1, 0)$ is. In line $3$ I've concluded that it is equal to $2$, so I can finally calculate the outer $f(0, 2)$. – Arthur Jan 01 '14 at 20:32
0

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$

drhab
  • 151,093