Funkcja rekurencyjna to pojęcie matematyczne obejmujące kilka znaczeń. Mamy funkcje rekurencyjne, funkcje pierwotnie rekurencyjne, funkcje elementarnie rekurencyjne, funkcje zdefiniowane za pomocą rekurencji prostej itp.

=Funkcje rekurencyjne= Funkcje rekurencyjne (nazywane również obliczalnymi) to funkcje należące do klasy Rek zdefiniowanej jak następuje.

Klasa Rek to najmniejsza rodzina funkcji częściowych o argumentach będących skończonymi ciągami liczb naturalnych ustalonej długości oraz wartościach naturalnych, która:

• zawiera funkcję zerową O: O(n)=0

• zawiera funkcję następnika S: S(n)=n+1

• zawiera funkcję identycznościową I: I(n)=n

• zawiera funkcje rzutowania P(k,m): P(k,m)(n(1),...,n(k))=n(m)

oraz jest zamknięta względem operacji

• składania funkcji: jeśli funkcje f(x(1),...,x(n)), g(1)(Y(1)),...,g(n)(Y(n)) należą do klasy Rek, to również funkcja h(Y(1),...,Y(n)) należy do klasy Rek (symbole Y(i) oznaczają zmienne lub ciągi zmiennych)

• rekursji prostej: jeśli funkcje f(X) oraz g(X,y,z) należą do klasy Rek, to do klasy tej należy również funkcja h(y,X) określona jak następuje: h(0,X)=f(X), h(y+1,X)=g(X,y,h(y,X)) (symbol X oznacza zmienną lub ciąg zmiennych)

• brania minimum ograniczonego: jeśli f(X,y) należy do Rek, to również funkcja h(X,t)=min{yRek (symbol X oznacza zmienną lub ciąg zmiennych). Warto wiedzieć, że operacja minimum nieograniczonego w postaci: h(X)=min{ f(X,y)=0} nie jest funkcją rekurencyjną, a nawet nie jest funkcją obliczalną. Innymi słowy, nie istnieje maszyna Turinga, dla której wiemy, że dla dowolnej funkcji rekurencyjnej f operacja brania jej minimum nieograniczonego zakończy sie w skończonym czasie. Aby można było oczekiwać istnienia takiej maszyny, funkcja rekurencyjna f musi spełniać dodatkowy warunek efektywności, tzn. dla każdego X musi istnieć takie y, że f(X,y)=0. Jednak dla takiej klasy funkcji (rekurencyjne, o własności efektywności), operacja minimum jest równoważna operacji minimum ograniczonego.

=Funkcja pierwotnie rekurencyjna= Pomijając w powyższej definicji operację brania minimum otrzymamy definicję klasy Prek złożonej z funkcji pierwotnie rekurencyjnych. Natomiast funkcje rekurencyjne można równoważnie zdefiniować jako te funkcje, dla których istnieje maszyna Turinga obliczająca ich wartości.

=Funkcja elementarnie rekurencyjna= Do napisania

=Zobacz też:=

• przegląd zagadnień z zakresu matematyki
• teoria rekursji
• teoria obliczeń
• złożoność obliczeniowa.

Teoria obliczeń | Logika | Rekursja

Berechenbare Funktion | Recursive function | Función recursiva | Fonction récursive | Endurkvæmt fall | Funzione ricorsiva | Recursividade | Рекурсивная функция | 递归函数