Пример 4

Рассмотрим функцию: f(x,y)  =  x^y. Поскольку f(x,0)  =  1, и f(x,y + 1)  =  xf(x,y)  =  g(x,y,f(x,y)), где g(x,y,z)  =  xz – примитивно рекурсивная функция (как композиция операции умножения и функции (I³₁, I³₃): N³  N²), то f(x,y) примитивно рекурсивна.