Obecnie czytam książkę Simona Thompsona The Craft of Functional Programming, a opisując rekurencję, wspomina on również o formie rekursji o nazwie Primitive Recursion.W jaki sposób rekursja pierwotna różni się od "normalnej" rekursji?
Czy możesz wyjaśnić, w jaki sposób ten typ rekursji różni się od "normalnych" funkcji rekursywnych?
Oto przykład prymitywnego funkcji rekursji (w Haskell):
power2 n
| n == 0 = 1
| n > 0 = 2 * power2(n - 1)
Uproszczoną odpowiedzią jest to, że prymitywne funkcje rekursywne to te, które definiuje się w kategoriach innych prymitywnych funkcji rekursywnych i rekurencja na strukturze liczb naturalnych. Liczby naturalne są koncepcyjnie tak:
data Nat
= Zero
| Succ Nat -- Succ is short for 'successor of', i.e. n+1
Oznacza to, że można rekursja na nich tak:
f Zero = ...
f (Succ n) = ...
Możemy napisać swój przykład jako:
power2 Zero = Succ Zero -- (Succ 0) == 1
power2 (Succ n) = 2 * power2 n -- this is allowed because (*) is primitive recursive as well
Skład funkcji pierwotnie rekurencyjnych jest także prymitywnym rekurencyjnym.
Innym przykładem jest liczb Fibonacciego:
fib Zero = Zero
fib (Succ Zero) = (Succ Zero)
fib (Succ [email protected](Succ n' )) = fib n + fib n' -- addition is primitive recursive
funkcji pierwotnie rekurencyjnych są naturalną odpowiedzią (matematyka) do powstrzymania problemu, odziera ją moc wykonaj dowolną rekurencję bez ograniczeń.
Rozważmy funkcję "zło"
f n
| n is an odd perfect number = true
| otherwise = f n+2
Czy f zakończyć? Nie możesz się dowiedzieć bez rozwiązania otwartego problemu, czy istnieją nieparzyste liczby doskonałe. To zdolność tworzenia takich funkcji sprawia, że problem z zatrzymaniem jest trudny.
Prymitywna rekursja jako konstrukcja nie pozwala na to; chodzi o to, by zakazać rzeczy "f n + 2", a jednocześnie pozostać tak elastycznym jak to tylko możliwe - nie można prymitywnie rekursywnie definiować f (n) w kategoriach f (n + 1).
Należy pamiętać, że fakt, że funkcja nie jest rekursywna, nie oznacza, że się nie kończy; Funkcja Ackermanna jest kanonicznym przykładem.
Jaka jest różnica między dobrze utworzoną rekursją a prymitywną rekurencją? – Hibou57
rekurencyjnego funkcje, które mogą być realizowane tylko przez robić pętle są prymitywne funkcje rekurencyjne.
Po prostu FYI (w oparciu o twój drugi post, nie ten), możesz zamieścić CV pod adresem http://careers.stackoverflow.com/ –
Wykonuj pętle ze zmienną pętli ściśle zmniejszającą. – ARi
... bardzo pomocne -_- –
Czy wolałbym skopiować i wkleić niektóre sekcje? Jeśli istnieje jakiś aspekt prymitywnej rekurencji, którego nie rozumiesz, lepszą odpowiedź można podać, ale "jak to się różni od ogólnej rekurencji" można odpowiedzieć jedynie patrząc na definicję w Wikipedii. –
OP próbuje się tutaj czegoś nauczyć. Czy chciałbyś skierować swoich uczniów do encyklopedii, gdybyś był nauczycielem matematyki? –