Funkcja rekurencyjna 📖 Wikipedia

Funkcjami pierwotnie rekurencyjnymi nazywamy funkcje:

• Funkcja zerowa

${\displaystyle Z\colon \mathbb {N} \to \mathbb {N} ,}$  zdefiniowana jako ${\displaystyle {\begin{matrix}Z(n)=0\end{matrix}}}$ 

• Funkcja następnika

${\displaystyle S\colon \mathbb {N} \to \mathbb {N} ,}$  zdefiniowana jako ${\displaystyle {\begin{matrix}S(n)=n+1\end{matrix}}}$ 

• Funkcja rzutowania

${\displaystyle I_{n}^{i}\colon \mathbb {N} ^{n}\to \mathbb {N} ,}$  zdefiniowana jako ${\displaystyle I_{n}^{i}(x_{1},\dots ,x_{n})=x_{i},\ i\leqslant n}$ 

oraz wszystkie funkcje zbudowane z funkcji pierwotnie rekurencyjnych za pomocą następujących metod kompozycji:

• Złożenia funkcji

Dla danych funkcji ${\displaystyle f\colon \mathbb {N} ^{k}\to \mathbb {N} }$  oraz ${\displaystyle g_{1},\dots ,g_{k}\colon \mathbb {N} ^{n}\to \mathbb {N} ,}$  złożeniem nazywamy funkcję

${\displaystyle h\colon \mathbb {N} ^{n}\to \mathbb {N} ,}$  zdefiniowaną jako ${\displaystyle h({\overline {n}})=f(g_{1}({\overline {n}}),\dots ,g_{k}({\overline {n}}))}$ 

• Rekursji prostej

Dla danych funkcji ${\displaystyle g\colon \mathbb {N} ^{n}\to \mathbb {N} }$  oraz ${\displaystyle h\colon \mathbb {N} ^{n+2}\to \mathbb {N} ,}$  złożeniem rekurencyjnym nazywamy funkcję

${\displaystyle f\colon \mathbb {N} ^{n+1}\to \mathbb {N} }$  zdefiniowaną jako ${\displaystyle {\begin{cases}f({\overline {n}},0)=g({\overline {n}})\\f({\overline {n}},S(m))=h(f({\overline {n}},m),{\overline {n}},m)\end{cases}}}$ 

Dodając do zbioru możliwych operacji operator minimalizacji otrzymujemy klasę funkcji częściowo rekurencyjnych:

• Operator minimalizacji

Dla danej funkcji ${\displaystyle f\colon \mathbb {N} ^{n+1}\to \mathbb {N} ,}$  definiujemy funkcję ${\displaystyle h\colon \mathbb {N} ^{n}\to \mathbb {N} }$  w ten sposób, że wartością ${\displaystyle h(x_{1},x_{2},\dots ,x_{n})}$  jest minimalne y takie, że

${\displaystyle \forall _{x\leqslant y}f(x,x_{1},x_{2},\dots ,x_{n})}$  jest zdefiniowane, oraz

${\displaystyle f(y,x_{1},x_{2},\dots ,x_{n})=0.}$ 

Ponieważ nie dla wszystkich wartości ${\displaystyle x_{1},\dots x_{n}}$  takie y musi istnieć, funkcje częściowe rekurencyjne mogą być (w przeciwieństwie do funkcji pierwotnie rekurencyjnych) funkcjami częściowymi.

Funkcję częściowo rekurencyjną, która jest zdefiniowana dla każdego argumentu, nazywamy funkcją rekurencyjną

Przykładem funkcji która jest rekurencyjna, ale nie jest pierwotnie rekurencyjna, jest funkcja Ackermanna.

Funkcjami elementarnie rekurencyjnymi nazywamy funkcje:

• funkcję następnika,
• funkcję odejmowania ograniczonego

${\displaystyle {\dot {-}}\colon \mathbb {N} ^{2}\to \mathbb {N} ,}$  zdefiniowaną jako ${\displaystyle {\dot {-}}(x,y)={\begin{cases}{0,\ x<y}\\{x-y,\ x\geqslant y}\end{cases}},}$ 

• funkcję potęgowania

${\displaystyle pow\colon \mathbb {N} ^{2}\to \mathbb {N} ,}$  zdefiniowaną jako ${\displaystyle {\begin{matrix}pow(x,y)=x^{y}\end{matrix}}.}$ 

oraz wszystkie funkcje zbudowane z powyższych trzech za pomocą złożenia funkcji i operatora minimalizacji ograniczonej.

Niech dana będzie pierwotnie rekurencyjna funkcja ${\displaystyle f\colon \mathbb {N} ^{n+1}\to \mathbb {N} .}$  Wówczas funkcje

${\displaystyle h_{1}\colon \mathbb {N} ^{n+1}\to \mathbb {N} ,}$  zdefiniowana jako ${\displaystyle h_{1}({\overline {n}},m)=\sum _{i=0}^{m}f({\overline {n}},i),}$ 

${\displaystyle h_{2}\colon \mathbb {N} ^{n+1}\to \mathbb {N} ,}$  zdefiniowana jako ${\displaystyle h_{2}({\overline {n}},m)=\prod _{i=0}^{m}f({\overline {n}},i)}$ 

są funkcjami pierwotnie rekurencyjnymi.

Analogicznie twierdzenie zachodzi dla funkcji elementarnie rekurencyjnych.

• ciąg Fibonacciego
• funkcja Ackermanna
• symbol Newtona

• teoria obliczeń
• teoria rekursji
• zbiór rekurencyjny
• złożoność obliczeniowa

• Mycka J., Teoria funkcji rekurencyjnych, wrzesień 2000, [1] (dostęp 27 sierpnia 2011).

• PiergiorgioP. Odifreddi PiergiorgioP., S. BarryS.B. Cooper S. BarryS.B., Recursive Functions, [w:] Stanford Encyclopedia of Philosophy, CSLI, Stanford University, 11 maja 2012, ISSN 1095-5054 [dostęp 2017-12-30]  (ang.). (Funkcje rekurencyjne)