Примити́вная реку́рсия, способ определения функций от натуральных аргументов с натуральными значениями. Говорят, что $(n+1)$-местная функция $f(x_1,\dots,x_n,y)$ получена примитивной рекурсией из $n$-местной функции $g(x_1,\dots,x_n)$ и $(n+2)$-местной функции $h(x_1,\dots, x_n, y, z)$, если для всех натуральных значений $x_1,\dots,x_n$, $y$ имеет место$$f(x_1,\dots,x_n,0)=g(x_1,\dots,x_n)$$и$$f(x_1,\dots,x_n,y+1)=h(x_1,\dots,x_n, y, f(x_1,\dots,x_n,y)).$$Для данных $g$ и $h$ такая функция $f$ всегда существует и единственна. При $n=0$ определяющие равенства для $f$ записываются в виде$$f(0)=a,\quad f(x+1)=h(x,f(x)).$$Фундаментальным свойством примитивной рекурсии является то, что при любом разумном уточнении понятия вычислимости функция $f$, полученная из вычислимых функций $g$ и $h$ с помощью примитивной рекурсии, сама вычислимая. Примитивная рекурсия – одно из основных правил порождения всех примитивно рекурсивных и всех частично рекурсивных функций из исходного набора простейших функций.