Rekurencja - Recursion

Wizualna forma rekurencji znana jako efekt Droste . Kobieta na tym obrazie trzyma przedmiot, który zawiera mniejszy obraz jej trzymającej identyczny przedmiot, który z kolei zawiera mniejszy obraz niej trzymającej identyczny przedmiot i tak dalej. 1904 Puszka kakaowa Droste , zaprojektowana przez Jana Misseta

Rekurencja (przymiotnik: rekurencyjna ) występuje, gdy rzecz jest definiowana w kategoriach samej siebie lub swojego typu. Rekurencja jest używana w różnych dyscyplinach, od językoznawstwa po logikę . Najczęstszym zastosowaniem rekurencji jest matematyka i informatyka , gdzie definiowana funkcja jest stosowana w ramach własnej definicji. Chociaż najwyraźniej definiuje to nieskończoną liczbę wystąpień (wartości funkcji), często odbywa się to w taki sposób, że nie może wystąpić nieskończona pętla lub nieskończony łańcuch odniesień.

Formalne definicje

Ouroboros , starożytny symbol przedstawiający węża lub smoka jedzącego własny ogon.

W matematyce i informatyce klasa obiektów lub metod wykazuje zachowanie rekurencyjne, gdy można ją zdefiniować za pomocą dwóch właściwości:

  • Prosty przypadek bazowy (lub przypadki) — scenariusz kończący, który nie używa rekurencji do uzyskania odpowiedzi
  • Rekurencyjne krok - zbiór zasad, który redukuje wszystkie kolejne przypadki wobec sprawy podstawowej.

Na przykład poniżej znajduje się rekurencyjna definicja przodka danej osoby . Przodkiem jest albo:

  • Rodzic ( przypadek podstawowy ) lub
  • Przodek rodzica ( krok rekurencyjny ).

Ciąg Fibonacciego jest kolejnym klasycznym przykładem rekurencji:

Fib(0) = 0 jako przypadek bazowy 1,
Fib(1) = 1 jako przypadek bazowy 2,
Dla wszystkich liczb całkowitych n > 1 , Fib( n ) = Fib( n − 1) + Fib( n − 2) .

Wiele aksjomatów matematycznych opiera się na regułach rekurencyjnych. Na przykład formalną definicję liczb naturalnych przez aksjomaty Peano można opisać jako: „Zero jest liczbą naturalną, a każda liczba naturalna ma następcę, który również jest liczbą naturalną”. Za pomocą tego przypadku bazowego i reguły rekurencyjnej można wygenerować zbiór wszystkich liczb naturalnych.

Inne rekurencyjnie zdefiniowane obiekty matematyczne obejmują silnie , funkcje (np. relacje rekurencyjne ), zbiory (np. zbiór trójkowy Cantora ) i fraktale .

Istnieje wiele bardziej żartobliwych definicji rekurencji; zobacz humor rekurencyjny .

Nieformalna definicja

Niedawno odświeżony zakwas , bulgoczący podczas fermentacji : przepis wymaga zakwasu pozostałego po ostatnim przygotowaniu tego samego przepisu.

Rekurencja to proces, przez który przechodzi procedura, gdy jeden z etapów procedury obejmuje wywołanie samej procedury. O procedurze, która przechodzi przez rekurencję, mówi się, że jest „rekurencyjna”.

Aby zrozumieć rekurencję, należy rozpoznać różnicę między procedurą a jej przebiegiem. Procedura to zestaw kroków oparty na zbiorze reguł, podczas gdy uruchomienie procedury polega na rzeczywistym przestrzeganiu reguł i wykonywaniu kroków.

Rekurencja jest związana z, ale nie tożsama z odwołaniem w specyfikacji procedury do wykonania jakiejś innej procedury.

Kiedy procedura jest zdefiniowana jako taka, natychmiast stwarza to możliwość nieskończonej pętli; rekursja może być prawidłowo użyta w definicji tylko wtedy, gdy dany krok jest pomijany w niektórych przypadkach, aby procedura mogła zostać zakończona.

Ale nawet jeśli jest właściwie zdefiniowana, procedura rekurencyjna nie jest łatwa do wykonania przez ludzi, ponieważ wymaga odróżnienia nowego od starego, częściowo wykonanego wywołania procedury; wymaga to pewnej administracji co do stopnia zaawansowania różnych jednoczesnych przypadków procedur. Z tego powodu definicje rekurencyjne są bardzo rzadkie w codziennych sytuacjach.

W języku

Lingwista Noam Chomsky , między innymi, argumentował, że brak górnej granicy liczby zdań gramatycznych w języku oraz brak górnej granicy długości zdań gramatycznych (poza ograniczeniami praktycznymi, takimi jak czas dostępny na wypowiedzenie jednego ), można wyjaśnić jako konsekwencję rekurencji w języku naturalnym.

Można to rozumieć w kategoriach rekurencyjnej definicji kategorii składniowej, takiej jak zdanie. Zdanie może mieć strukturę, w której po czasowniku występuje inne zdanie: Dorota uważa, że ​​czarownice są niebezpieczne , w którym zdanie czarownice są niebezpieczne występuje w większym. Tak więc zdanie można zdefiniować rekurencyjnie (z grubsza) jako coś o strukturze zawierającej frazę rzeczownikową, czasownik i opcjonalnie inne zdanie. To tak naprawdę tylko szczególny przypadek matematycznej definicji rekurencji.

Daje to sposób na zrozumienie kreatywności języka — nieograniczonej liczby zdań gramatycznych — ponieważ od razu przewiduje, że zdania mogą mieć dowolną długość: Dorota myśli, że Toto podejrzewa, iż Blaszany Człowiek powiedział, że... . Istnieje wiele struktur poza zdaniami, które można definiować rekurencyjnie, a zatem na wiele sposobów, w jakie zdanie może osadzić instancje jednej kategorii w drugiej. Z biegiem lat języki ogólnie okazały się podatne na tego rodzaju analizy.

Ostatnio jednak ogólnie przyjęta idea, że ​​rekurencja jest istotną właściwością ludzkiego języka, została zakwestionowana przez Daniela Everetta na podstawie jego twierdzeń o języku Pirahã . Andrew Nevins, David Pesetsky i Cilene Rodrigues są wśród wielu, którzy argumentowali przeciwko temu. W każdym razie można argumentować, że literackie odniesienie do siebie jest inne niż rekurencja matematyczna lub logiczna.

Rekurencja odgrywa kluczową rolę nie tylko w składni, ale także w semantyce języka naturalnego . Na przykład słowo i może być rozumiane jako funkcja, którą można zastosować do znaczeń zdań w celu utworzenia nowych zdań, a także do znaczeń wyrażeń rzeczownikowych, znaczeń wyrażeń czasownikowych i innych. Może również dotyczyć czasowników nieprzechodnich, czasowników przechodnich lub czasowników dwuprzechodnich. Aby zapewnić dla niego pojedynczą denotację, która jest odpowiednio elastyczna i jest zwykle zdefiniowana tak, że może przyjmować dowolne z tych różnych typów znaczeń jako argumenty. Można to zrobić, definiując go dla prostego przypadku, w którym łączy zdania, a następnie definiując pozostałe przypadki rekurencyjnie w kategoriach prostego.

Rekurencyjne gramatyka jest formalnym gramatyki, który zawiera rekurencyjne zasad produkcji .

Rekurencyjny humor

Rekurencyjna strona Wikipedii

Rekurencja jest czasami używana w humorystyczny sposób w podręcznikach informatyki, programowania, filozofii lub matematyki, na ogół przez podanie okrągłej definicji lub samoodniesienia , w których domniemany krok rekurencyjny nie zbliża się do przypadku podstawowego, ale zamiast tego prowadzi do nieskończonego regresu . Nie jest niczym niezwykłym, że takie książki zawierają w swoim glosariuszu żart w stylu:

Rekursja, zobacz Rekursja .

Odmianą znajduje się na stronie 269 w indeksie niektórych edycjach Brian Kernighan i Dennis Ritchie „s book Język ANSI C ; pozycja indeksu rekurencyjnie odwołuje się do siebie („rekurencja 86, 139, 141, 182, 202, 269”). Wczesne wersje tego żartu można znaleźć w Let's talk Lisp Laurenta Siklóssy'ego (opublikowane przez Prentice Hall PTR 1 grudnia 1975 r., z datą praw autorskich w 1976 r.) oraz w Software Tools autorstwa Kernighana i Plaugera (opublikowane przez Addison-Wesley Professional na 11 stycznia 1976). Żart pojawia się również w The UNIX Programming Environment autorstwa Kernighana i Pike'a. Nie pojawiają się w pierwszej edycji The C Programming Language . Żart jest częścią folkloru programowania funkcjonalnego i był już szeroko rozpowszechniony w społeczności programowania funkcjonalnego przed publikacją wspomnianych książek.

Inny żart brzmi: „Aby zrozumieć rekurencję, musisz zrozumieć rekurencję”. W anglojęzycznej wersji wyszukiwarki internetowej Google podczas wyszukiwania hasła „rekurencja” witryna sugeruje „Czy chodziło Ci o: rekurencję ”. Alternatywna forma jest następująca, od Andrew Plotkina : „Jeśli już wiesz, co to jest rekurencja, po prostu zapamiętaj odpowiedź. W przeciwnym razie znajdź kogoś, kto stoi bliżej Douglasa Hofstadtera niż ty, a następnie zapytaj go, co to jest rekurencja”.

Akronimy rekurencyjne to inne przykłady humoru rekurencyjnego. Na przykład PHP oznacza „PHP Hypertext Preprocessor”, WINE oznacza „WINE Is Not an Emulator”, GNU oznacza „GNU's not Unix”, a SPARQL oznacza „SPARQL Protocol and RDF Query Language”.

W matematyce

Sierpiński trójkąt -a ogranicza rekursji trójkątów stanowiących fraktal

Zbiory zdefiniowane rekurencyjnie

Przykład: liczby naturalne

Kanoniczny przykład zbioru zdefiniowanego rekurencyjnie dają liczby naturalne :

0 jest w
jeśli n jest w , to n + 1 jest w
Zbiór liczb naturalnych jest najmniejszym zbiorem spełniającym poprzednie dwie własności.

W logice matematycznej aksjomaty Peano (lub postulaty Peano lub aksjomaty Dedekinda-Peano) są aksjomatami liczb naturalnych przedstawionych w XIX wieku przez niemieckiego matematyka Richarda Dedekinda i włoskiego matematyka Giuseppe Peano . Aksjomaty Peano definiują liczby naturalne odnoszące się do rekurencyjnej funkcji następnika oraz dodawania i mnożenia jako funkcji rekurencyjnych.

Przykład: Procedura sprawdzająca

Innym interesującym przykładem jest zbiór wszystkich „dowodliwych” zdań w systemie aksjomatycznym, które są zdefiniowane w terminach procedury dowodowej, która jest indukcyjnie (lub rekurencyjnie) zdefiniowana w następujący sposób:

  • Jeśli zdanie jest aksjomatem, jest to zdanie dające się udowodnić.
  • Jeśli zdanie można wyprowadzić z prawdziwych zdań osiągalnych za pomocą reguł wnioskowania, jest to zdanie dowodliwe.
  • Zbiór zdań dowodzących to najmniejszy zbiór zdań spełniających te warunki.

Skończone zasady podziału

Reguły skończonego podziału są geometryczną formą rekurencji, którą można wykorzystać do tworzenia obrazów podobnych do fraktali. Reguła podziału zaczyna się od zbioru wielokątów oznaczonych skończoną liczbą etykiet, a następnie każdy wielokąt jest dzielony na mniejsze wielokąty oznaczone w sposób zależny tylko od etykiet oryginalnego wielokąta. Ten proces można powtarzać. Standardowa technika "środkowych trzecich" przy tworzeniu zbioru Cantora jest regułą podziału, podobnie jak podział barycentryczny .

Rekurencja funkcjonalna

Funkcja może być rekurencyjnie definiowane siebie. Znanym przykładem jest ciąg liczb Fibonacciego : F ( n ) = F ( n − 1) + F ( n − 2). Aby taka definicja była użyteczna, musi dać się sprowadzić do nierekurencyjnie zdefiniowanych wartości: w tym przypadku F (0) = 0 i F (1) = 1.

Słynną funkcją rekurencyjną jest funkcja Ackermanna , która w przeciwieństwie do ciągu Fibonacciego nie może być wyrażona bez rekurencji.

Dowody obejmujące definicje rekurencyjne

Zastosowanie standardowej techniki dowodu przez przypadki do rekurencyjnie zdefiniowanych zbiorów lub funkcji, jak w poprzednich rozdziałach, daje indukcję strukturalną — potężne uogólnienie indukcji matematycznej szeroko stosowanej do wyprowadzania dowodów w logice matematycznej i informatyce.

Optymalizacja rekurencyjna

Programowanie dynamiczne to podejście do optymalizacji, które odtwarza problem optymalizacji wielookresowej lub wieloetapowej w formie rekurencyjnej. Kluczowym rezultatem w programowaniu dynamicznym jest równanie Bellmana , które zapisuje wartość problemu optymalizacyjnego we wcześniejszym czasie (lub wcześniejszym kroku) pod względem jego wartości w późniejszym czasie (lub późniejszym kroku).

Twierdzenie o rekurencji

W teorii mnogości jest to twierdzenie gwarantujące istnienie funkcji zdefiniowanych rekurencyjnie. Mając dany zbiór X , element a zbioru X i funkcję f : XX , twierdzenie stwierdza, że ​​istnieje unikalna funkcja (gdzie oznacza zbiór liczb naturalnych zawierających zero) taką, że

dla dowolnej liczby naturalnej n .

Dowód wyjątkowości

Weź dwie funkcje i takie, że:

gdzie a jest elementem X .

Za pomocą indukcji matematycznej można udowodnić, że F ( n ) = G ( n ) dla wszystkich liczb naturalnych n :

Przypadek bazowy : F (0) = a = G (0) więc równość obowiązuje dla n = 0 .
Krok indukcyjny : Załóżmy, że dla niektórych F ( k ) = G ( k ) . Wtedy F ( k + 1) = f ( F ( k )) = f ( G ( k )) = G ( k + 1 ) .
Stąd F ( k ) = G ( k ) implikuje F ( k +1)= G ( k +1) .

Przez indukcję F ( n ) = G ( n ) dla wszystkich .

W informatyce

Powszechną metodą upraszczania jest podzielenie problemu na podproblemy tego samego typu. Jako technika programowania komputerowego nazywa się to dziel i rządź i jest kluczem do projektowania wielu ważnych algorytmów. Dziel i rządź służy jako odgórne podejście do rozwiązywania problemów, w którym problemy są rozwiązywane przez rozwiązywanie coraz mniejszych instancji. Odwrotnym podejściem jest programowanie dynamiczne . To podejście służy jako podejście oddolne, w którym problemy są rozwiązywane przez rozwiązywanie coraz większych instancji, aż do osiągnięcia pożądanego rozmiaru.

Klasycznym przykładem rekurencji jest definicja funkcji silni , podana tutaj w kodzie C :

unsigned int factorial(unsigned int n) {
    if (n == 0) {
        return 1;
    } else {
        return n * factorial(n - 1);
    }
}

Funkcja wywołuje się rekurencyjnie na mniejszej wersji danych wejściowych (n - 1)i mnoży wynik wywołania rekurencyjnego przez n, aż do osiągnięcia przypadku bazowego , analogicznie do matematycznej definicji silni.

Przykładem rekurencji w programowaniu komputerowym jest zdefiniowanie funkcji w kategoriach prostszych, często mniejszych wersji samej siebie. Rozwiązanie problemu jest następnie obmyślane przez połączenie rozwiązań uzyskanych z prostszych wersji problemu. Jednym z przykładów zastosowania rekurencji są parsery dla języków programowania. Wielką zaletą rekurencji jest to, że nieskończony zbiór możliwych zdań, projektów lub innych danych może być definiowany, analizowany lub wytwarzany przez skończony program komputerowy.

Relacje rekurencyjne to równania, które rekurencyjnie definiują jedną lub więcej sekwencji. Niektóre specyficzne rodzaje relacji rekurencyjnych można „rozwiązać”, aby uzyskać definicję nierekurencyjną (np. wyrażenie w formie zamkniętej ).

Zastosowanie rekurencji w algorytmie ma zarówno zalety, jak i wady. Główną zaletą jest zazwyczaj prostota instrukcji. Główną wadą jest to, że użycie pamięci przez algorytmy rekurencyjne może rosnąć bardzo szybko, co czyni je niepraktycznymi w przypadku większych instancji.

W biologii

Kształty, które wydają się być tworzone przez procesy rekurencyjne, czasami pojawiają się w roślinach i zwierzętach, na przykład w rozgałęzionych strukturach, w których jedna duża część rozgałęzia się na dwie lub więcej podobnych mniejszych części. Jednym z przykładów są brokuły Romanesco .

W sztuce

Rekurencyjne lalek: oryginalny zestaw matrioszki przez Zvyozdochkin i Malyutin 1892
Czołowa Giotto jest Stefaneschi Tryptyku 1320, rekurencyjnie zawiera obraz siebie (podtrzymywany na rysunku klęczącej na panelu centralnym).

Rosyjska lalka lub lalka Matrioszka jest fizycznym artystycznym przykładem koncepcji rekurencyjnej.

Rekurencja zostały wykorzystane w obrazach od Giotto „s Stefaneschi Tryptyku , wykonane w 1320 roku Jego centralny panel zawiera figurę klęczącego kardynała Stefaneschi, trzymając się sam tryptyk jako ofiarę.

MC Escher „s Print Gallery (1956) to print, który przedstawia wypaczony miasto zawierający galerię, która rekurencyjnie zawierających zdjęcia, i tak ad infinitum .

Zobacz też

Bibliografia

Bibliografia

Zewnętrzne linki