Ackermann functions
A convenient example is
f[1, n_] := n; f[m_, 1] := f[m - 1, 2]
f[m_, n_] := f[m - 1, f[m, n - 1] + 1]
The original function constructed by Wilhelm Ackermann around 1926 is essentially
f[1, x_, y_] := x + y;
f[m_, x_, y_] := Nest[f[m - 1, x, #] &, x, y - 1]
or
f[m_, x_, y_]:= Nest[Function[z, Nest[#, x, z - 1]] &, x + # &, m - 1][y]
For successive m (following the so-called Grzegorczyk hierarchy) this is x + y, x y, xy, Nest[x# &, 1, y], .... f[4, x, y] can also be written Array[x &, y, 1, Power] and is sometimes called tetration and denoted x↑↑y.