Примитивті – рекурсивті функциялар

Қ андай да бір меншікті тү рде анық талғ ан функция рекурсивті деп аталады. Олардың анық талу облысы – 0 жә не натурал сандар жиыны.

Қ арапайым немесе элементар рекурсивті функциялар:

1. Салдар функциясы

2. Тұ рақ ты функция (кө біне бұ л 0)

3. Мә ндес функция

Бір рекурсивті функцияларды екінші рекурсивті функциялар аргументтерінің орнымен алмастыру суперпозиция операциясы деп аталады.

M аргументті n функция жә не n аргументті функциясы берілсін. Онда суперпозиция операциясының нә тижесінде m аргументті функция аламыз:

функциялары берілсін. Онда примитивті – рекурсивті операциясы келесі формула бойынша анық талады:

Функция примитивті – рекурсивті деп аталады, егер оны элементар рекурсивті функциялардың, саны шектеулі суперпозиция жә не прмитивті – рекурсия операцияларының кө мегімен ө рнектеуге болса.

Функция дербес деп аталады, егер ол аргументтердің барлық мә ндерінде анық талмаса.