Przykładem funkcji która jest rekurencyjna, ale nie jest pierwotnie rekurencyjna, jest funkcja Ackermanna.
Funkcja elementarnie rekurencyjna Funkcjami elementarnie rekurencyjnymi nazywamy funkcje: funkcję następnika, funkcję odejmowania ograniczonego zdefiniowaną jako funkcję potęgowania zdefiniowaną jako
oraz wszystkie funkcje zbudowane z powyższych trzech za pomocą złożenia funkcji i operatora minimalizacji ograniczonej.
Twierdzenie o zamkniętości funkcji pierwotnie rekurencyjnych ze względu na sumę i iloczyn Niech dana będzie pierwotnie rekurencyjna funkcja Wówczas funkcje zdefiniowana jako zdefiniowana jako
są funkcjami pierwotnie rekurencyjnymi.
Analogicznie twierdzenie zachodzi dla funkcji elementarnie rekurencyjnych.
Przykłady funkcji rekurencyjnych ciąg Fibonacciego funkcja Ackermanna symbol Newtona
Zobacz też teoria obliczeń teoria rekursji zbiór rekurencyjny złożoność obliczeniowa
Bibliografia Mycka J., Teoria funkcji rekurencyjnych, wrzesień 2000, (dostęp 27 sierpnia 2011).
Linki zewnętrzne
Kategoria:Rekurencja