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

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

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

$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 9780821802458, MR 0281602