Операція примітивної рекурсії

Опера́ція приміти́вної реку́рсії — двомісна операція, широко вживана в теорії рекурсивних функцій. Пара рекурсивних функцій: перша функція від ${\displaystyle m+2}$ змінних ${\displaystyle h(x_{1},...,x_{m+1},\ x_{m+2})}$, а інша функція від ${\displaystyle m}$ змінних ${\displaystyle g(x_{1},...,x_{m})}$ , утворює функцію від ${\displaystyle m+1}$ змінних ${\displaystyle f(x_{1},...,x_{m+1})}$ за такою схемою:

${\displaystyle f(x_{1},...,x_{m},\ 0)=g(x_{1},...,x_{m})}$

${\displaystyle f(x_{1},...,x_{m},\ n+1)=h(x_{1},...,x_{m},\ n,\ f(x_{1},...,x_{m},\ n))}$

Див. також

• Рекурсивна функція

Джерела

• Енциклопедія кібернетики : у 2 т. / за ред. В. М. Глушкова. — Київ : Гол. ред. Української радянської енциклопедії, 1973. т. 2, ст. 129.
• Jensen, Ronald B.; Karp, Carol (1971), Primitive recursive set functions, Axiomatic Set Theory, Proc. Sympos. Pure Math., т. XIII, Part I, Providence, R.I.: Amer. Math. Soc., с. 143—176, ISBN , MR 0281602