Funkcja rekurencyjna

Z Wikipedii

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

Spis treści 1 Funkcja pierwotnie rekurencyjna 1.1 Definicja funkcji pierwotnie rekurencyjnej 1.2 Twierdzenie o zamkniętości funkcji pierwotnie rekurencyjnych ze względu na sumę i iloczyn 2 Funkcja częściowo rekurencyjna 2.1 Definicja funkcji częsciowo rekurencyjnej 2.2 Definicja operatora minimalizacji 3 Funkcja rekurencyjna 3.1 Definicja funkcji rekurencyjnej 4 Funkcja elementarnie rekurencyjna 4.1 Definicja funkcji elementarnie rekurencyjnej 4.2 Definicja operatora minimalizacji ograniczonej 4.3 Twierdzenie o zamkniętości funkcji elementarnie rekurencyjnych ze względu na sumę i iloczyn 5 Nietrywialne funkcje rekurencyjne 6 Zobacz też 7 Literatura

[edytuj] Funkcja pierwotnie rekurencyjna

[edytuj] Definicja funkcji pierwotnie rekurencyjnej

Funkcjami pierwotnie rekurencyjnymi nazywamy funkcje:

• funkcję zerowania

• funkcję następnika

• funkcję rzutowania

oraz inne funkcje zbudowane z powyższych trzech za pomocą:

• złożenia funkcji

Niech dane będą pewne funkcje pierwotnie rekurencyjne ,
wówczas tak zdefiniowana funkcja 
jest pierwotnie rekurencyjna.

• rekursji prostej

Niech dane będą pewne dwie funkcje pierwotnie rekurencyjne ,
wówczas tak zdefiniowana funkcja

jest funkcją pierwotnie rekurencyjną.

[edytuj] Twierdzenie o zamkniętości funkcji pierwotnie rekurencyjnych ze względu na sumę i iloczyn

Niech dana będzie pierwotnie rekurencyjna funkcja ,
wówczas tak zdefiniowane funkcje
,

są funkcjami pierwotnie rekurencyjnymi.

[edytuj] Funkcja częściowo rekurencyjna

[edytuj] Definicja funkcji częsciowo rekurencyjnej

Funkcja f jest częściowo rekurencyjna jeśli jest zdefiniowana wychodząc z funkcji zerowania, funkcji następnika, złożenia funkcji, rekursji prostej lub operatora minimalizacji.

[edytuj] Definicja operatora minimalizacji

Niech dana będzie funkcja postaci ,
wówczas istnieje funkcja g częsciowo obliczalna zdefiniowana następująco:
.

Operator minimalizacji jest zdefiniowany następująco: .

[edytuj] Funkcja rekurencyjna

[edytuj] Definicja funkcji rekurencyjnej

Mówimy że funkcja f jest rekurencyjna jeśli jest częsciowo rekurencyjna oraz f jest wszędzie zdefiniowna co równoważne jest z tym że operator minimalizcji funkcji rekurencyjnej musi być określony/zwracać wynik dla każdego możliwego argumentu.

[edytuj] Funkcja elementarnie rekurencyjna

[edytuj] Definicja funkcji elementarnie rekurencyjnej

Funkcjami elementarnie rekurencyjnymi nazywamy funkcje:

• funkcję następnika
• funkcję odejmowania ograniczonego

• funkcję potęgowania

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

[edytuj] Definicja operatora minimalizacji ograniczonej

[edytuj] Twierdzenie o zamkniętości funkcji elementarnie rekurencyjnych ze względu na sumę i iloczyn

Niech dana będzie elementarnie rekurencyjna funkcja ,
wówczas tak zdefiniowane funkcje
,

są funkcjami elementarnie rekurencyjnymi.

[edytuj] Nietrywialne funkcje rekurencyjne

• symbol Newtona
• ciąg Fibonacciego
• funkcja Ackermanna

[edytuj] Zobacz też

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

[edytuj] Literatura

• Mycka J. Teoria funkcji rekurencyjnych. Wrzesień 2000. [1] (dostęp 1 października 2006)