Finding formulas for a recursive function from $\Bbb{N} \times \Bbb{N}$ to $\Bbb{N}$ Define $B: \Bbb{N} \times \Bbb{N} \to \Bbb{N}$ by the recursive formula:
$$B(0,x) = x+1$$
$$B(y+1,0) = B(y,1)$$
$$B(y +1,x +1) = B(y, B(y +1,x))$$
The assignment asks me to find simple formulas for $B(1,x), B(2,x) \text{ and } B(3,x)$. I think I could do this if I understood how this function actually works.
I've tried sticking in natural numbers but I don't quite follow.
If $x=1$ and $y=2$,
$B(0,1) = 1+1 =2$
$B(y+1,0) = B(2+1,0) = B(3,0) = B(2,1)$
$B(y +1,x +1) = B(2 +1,1 +1) = B(3,2) = B(2, B(2 +1,1)) = B(2, B(3,1))$
What is $B(2,1)$ and $B(3,1)$? Do I even need to have values for those to understand the problem?
 A: I think you're picturing it backwards, pluggin the values you care about into the $x$ and $y$ in the definition. That's not going to work: instead, you want to use the definition to "build up to" the values you care about.
For example, let's say we want to compute $B(2,0)$. We have: $$B(2,0)=B(1+1,0)\color{blue}{=}B(1,1)=B(0+1,0+1)\color{red}{=}B(0, B(1,0))$$ where again the red equality comes from the third clause of the definition (with $y=0,x=0$) and the blue equality comes from the second clause of the definition (with $y=1$).
So now we have a "sub-computation" to perform: we have to compute $B(1,0)$ before we can finish computing $B(2,0)$. As before we have $$B(1,0)=B(0+1,0)\color{blue}{=}B(0,1)\color{green}{=}2$$ where the blue equality comes from the second clause of the definition (with $y=0$) and the green equality comes from the first clause of the definition (with $x=1$). Note that this is new: we couldn't apply the first clause of the definition until now.
And now we're ready to finish our computation of $B(2,0)$. We already showed that $B(2,0)=B(0,B(1,0))$, so by our above sub-computation we get $$B(2,0)=B(0,2)\color{green}{=}3$$ where again the green equality comes from the first clause of the definition (with $x=2$).

Computing $B(2,1)$ takes longer, but the idea is the same. At each stage, apply one of the relevant clauses to break down your current $B$-expression into one with smaller entries. When one entry or the other is zero, you use either the first or second clause; if neither coordinate is zero, you use the third clause. The values of $x$ and $y$ you consider change with each step. It might help to rephrase the clauses in terms of subtraction, so that e.g. the third clause would be

"If $u,v>0$ then $B(u,v)=B(u-1, B(u, v-1))$,"

but this is somewhat messier in the long run.
A: Suppose we know all the $B(y, \dots)$ values for a given value of $y$. The third rule tells us that if we know $B(y+1,x)$ then we can find $B(y+1,x+1)$ by using $B(y+1,x)$ as an index into the $B(y,\dots)$ values.
If we knew $B(y+1,0)$ then we could use this to find $B(y+1,1)$, then use this to find $B(y+1,2)$ and so on. But the second rule tells us how to find $B(y+1,0)$. And the first rule tells us all the $B(0,\dots)$ values to get us started.
So $B(0,\dots)=1,2,3,4,\dots$. And $B(1,0)=B(0,1)=2$. So ...
$B(1,1) = B(0,2) =3\\B(1,2) = B(0,3) =4\\B(1,3) = B(0,4) =5$
and so on. We see a pattern emerging ... $B(1,x)=x+2$.
And now that we know $B(1,\dots)$ we can use the same method to find $B(2,\dots)$ ...
A: I think recasting every equation in the definition to $B(y,x)$ instead of $B(y+1,x+1)$ for example may be more intuitive.
$$B(0,x)=x+1$$
$$B(y,0)=B(y-1,1)$$
$$B(y,x)=B(y-1,B(y,x-1))$$
or all together:
$$B(y,x)=\begin{cases}x+1,&y=0\\B(y-1,1),&y\ne0\text{ and }x=0\\B(y-1,B(y,x-1)),&y\ne0\text{ and }x\ne0\end{cases}$$
Now you can simply plug into the above. For example, with $B(2,1)$ we get:
\begin{align}B(2,1)&=B(1,B(2,0))\\B(2,0)&=B(1,1)\\B(1,1)&=B(0,B(1,0))\\B(1,0)&=B(0,1)\\B(0,1)&=2\end{align}
and you can plug that back in and work it out further.
