• Artykuły
  • Forum
  • Ciekawostki
  • Encyklopedia
  • Rekurencja

    Przeczytaj także...
    Rekurencja ogonowa, zwana też Tail call lub prawostronną jest rodzajem rekurencji, w której ostatnia operacja wykonywana przez funkcję to rekurencyjne wywołanie samej siebie lub zwrócenie końcowego wyniku. Taka funkcja może zostać łatwo zamieniona na iterację, zarówno ręcznie, jak i automatycznie, co redukuje wielkość stosu oraz zwiększa wydajność. Ta technika iteracyjnego wykonywania obliczeń jest powszechna w programowaniu funkcyjnym promującym używanie rekurencji, która w przeciwnym wypadku zajęłaby cały dostępny stos.Dziel i zwyciężaj (ang. divide and conquer) – jedna z głównych metod projektowania algorytmów w informatyce, prowadząca do bardzo efektywnych rozwiązań. Nazwa pochodzi od łacińskiej sentencji dziel i rządź (łac. divide et impera). W strategii tej problem dzieli się rekurencyjnie na dwa lub więcej mniejszych podproblemów tego samego (lub podobnego) typu tak długo, aż fragmenty staną się wystarczająco proste do bezpośredniego rozwiązania. Z kolei rozwiązania otrzymane dla podproblemów scala się, uzyskując rozwiązanie całego zadania.
    Teoria złożoności obliczeniowej – dział teorii obliczeń, którego głównym celem jest określanie ilości zasobów potrzebnych do rozwiązania problemów obliczeniowych. Rozważanymi zasobami są takie wielkości jak czas, pamięć lub liczba procesorów.
    Przykład rekurencji w sztuce użytkowej (Efekt Droste)

    Rekurencja, zwana także rekursją (ang. recursion, z łac. recurrere, przybiec z powrotem) – odwoływanie się np. funkcji lub definicji do samej siebie.

    W logice wnioskowanie rekurencyjne opiera się na założeniu istnienia pewnego stanu początkowego oraz zdania (lub zdań) stanowiącego podstawę wnioskowania (przy czym, aby cały dowód był poprawny, zarówno reguła, jak i stan początkowy muszą być prawdziwe). Istotą rekurencji jest tożsamość dziedziny i przeciwdziedziny reguły wnioskowania, wskutek czego wynik wnioskowania może podlegać tej samej regule zastosowanej ponownie.

    Trójkąt Sierpińskiego (znany też jako uszczelka Sierpińskiego) – jeden z najprostszych fraktali. Znany był na długo przed powstaniem tego pojęcia (patrz Benoit Mandelbrot). Konstrukcja tego zbioru była podana przez polskiego matematyka Wacława Sierpińskiego w 1915.Definicja (z łac. definitio; od czas. definire: de + finire, "do końca, granicy"; od finis: granica, koniec) – wypowiedź o określonej budowie, w której informuje się o znaczeniu pewnego wyrażenia przez wskazanie innego wyrażenia należącego do danego języka i posiadającego to samo znaczenie.

    Na prostym przykładzie: reguła: każdy ojciec jest starszy od swojego syna; każdy ojciec jest czyimś synem stan początkowy: jestem 22-letnim mężczyzną teza: ojciec ojca mojego ojca jest starszy ode mnie dowód:

    1. mój ojciec jest starszy ode mnie
    2. mój ojciec jest czyimś synem
    3. ojciec mojego ojca jest starszy od mojego ojca
    4. ojciec mojego ojca jest czyimś synem
    5. itd.

    Na przykładzie zastosowań matematycznych poniższa definicja ciągu Fibonacciego jest rekurencyjna:

    Derekursywacja – przekształcenie algorytmu rekursyjnego w odpowiadający mu funkcjonalnie algorytm iteracyjny. Choć algorytmy rekurencyjne bywają prostsze do zrozumienia, to obarczone są jednak zwykle dużą złożonością obliczeniową lub pamięciową (zob. asymptotyczne tempo wzrostu): algorytmy iteracyjne bliższe są zwykle architekturze procesorów (a dokładniej ich modelom programowym), przez co zwykle są szybsze i zużywają mniej pamięci (największym obciążeniem jest zwykle kosztowna obsługa stosu wywołań).Rachunek lambda – system formalny używany do badania zagadnień związanych z podstawami matematyki jak rekurencja, definiowalność funkcji, obliczalność, podstawy matematyki np. definicja liczb naturalnych, wartości logicznych itd. Rachunek lambda został wprowadzony przez Alonzo Churcha i Stephena Cole’a Kleene’ego w 1930 roku.
      dla 

    lub inaczej:

    Stanford Encyclopedia of Philosophy (SEP) jest ogólnie dostępną encyklopedią internetową filozofii opracowaną przez Stanford University. Każde hasło jest opracowane przez eksperta z danej dziedziny. Są wśród nich profesorzy z 65 ośrodków akademickich z całego świata. Autorzy zgodzili się na publikację on-line, ale zachowali prawa autorskie do poszczególnych artykułów. SEP ma 1260 haseł (stan na 20 stycznia 2011). Mimo, że jest to encyklopedia internetowa, zachowano standardy typowe dla tradycyjnych akademickich opracowań, aby zapewnić jakość publikacji (autorzy-specjaliści, recenzje wewnętrzne).PHP – obiektowy język programowania zaprojektowany do generowania stron internetowych i budowania aplikacji webowych w czasie rzeczywistym.

    gdyż definiuje funkcję odwołując się w definicji do niej samej.

    Symbol Newtona ( n k ) {displaystyle {n choose k}} (nazywany też współczynnikiem dwumianowym, czytany n nad k, n po k lub k z n) jest to funkcja dwóch argumentów całkowitych nieujemnych, zdefiniowana jako:Funkcja Ackermanna jest funkcją matematyczną odkrytą przez Wilhelma Ackermanna w 1928 roku. Cechą charakterystyczną tej dwuargumentowej funkcji jest jej nadzwyczaj szybki wzrost. Funkcja Ackermanna jest prostym przykładem funkcji rekurencyjnej, niebędącej funkcją pierwotnie rekurencyjną. Funkcje pierwotnie rekurencyjne to większość znanych funkcji, między innymi dodawanie, funkcja wykładnicza itp.

    Każda definicja rekurencyjna potrzebuje przynajmniej jednego przypadku bazowego (nie rekurencyjnego), w tym przypadku są to wartości dla 0 i 1. W przeciwnym wypadku nigdy się nie zakończy.

    Dla przykładu, obliczenie wygląda następująco:

    Innym przykładem jest wyliczanie największego wspólnego dzielnika za pomocą algorytmu Euklidesa:

    MathWorld – encyklopedia matematyczna online, sponsorowana przez Wolfram Research, twórcę i producenta programu Mathematica; współsponsorem jest National Science Foundation (National Science Digital Library).Silnią liczby naturalnej n (w notacji matematycznej: n!, co czytamy „n silnia”) nazywamy iloczyn wszystkich liczb naturalnych nie większych niż n. Oznaczenie n! wprowadził w 1808 roku Christian Kramp.
    1. dla     oznacza tu resztę z dzielenia przez

    lub inaczej:

    Rekursja pośrednia to taka rekursja, w której jednocześnie jest definiowanych kilka (tzn. więcej niż jeden) obiektów, które nawzajem "z siebie korzystają".Wielomiany Czebyszewa – układ wielomianów ortogonalnych tworzący bazę wielomianów, nazwa pochodzi od nazwiska Pafnutija Czebyszewa.

    Rekurencja jest podstawową techniką wykorzystywaną w funkcyjnych językach programowania. Należy jednak zachować ostrożność przy używaniu rekurencji w rzeczywistych programach. Ryzyko istnieje szczególnie przy przetwarzaniu dużej ilości głęboko zagnieżdżonych danych.

    1 (jeden, jedność) – liczba naturalna następująca po 0 i poprzedzająca 2. 1 jest też cyfrą wykorzystywaną do zapisu liczb w różnych systemach, np. w dwójkowym (binarnym), ósemkowym, dziesiętnym i szesnastkowym systemie liczbowym. Każda liczba całkowita jest podzielna przez 1.Operator paradoksalny (operator punktu stałego) - funkcja w rachunku lambda, która dla każdej funkcji tworzy jej punkt stały:

    Jeśli program nie jest w rzeczywistości rekurencyjny, to rekurencja może poważnie zwiększyć złożoność obliczeniową. Ponadto zawsze zwiększa ona zapotrzebowanie programu na pamięć operacyjną (chyba że zostanie użyta możliwa w pewnych przypadkach optymalizacja zwana rekurencją ogonową), gdyż wymaga zapamiętania m.in. adresów powrotu, pozwalających programowi „zorientować się”, do którego miejsca ma wrócić po zakończeniu jednego z wywołań rekurencyjnych. Inną częstą wadą rekurencji jest kompletnie niezależne rozwiązywanie podproblemów, tak, że czasem jeden problem jest rozwiązywany w kilku miejscach rozwinięcia rekurencji, np. w powyższym przykładzie obliczania niepotrzebnie jest dwukrotnie obliczana wartość (porównaj: programowanie dynamiczne). Takie problemy nie pojawiają się przy drugim z przykładów. Jednak, niezaprzeczalną zaletą rekurencji jest przejrzystość programów, które z niej korzystają.

    Cecha podzielności – metoda umożliwiająca stwierdzenie, czy dana liczba jest podzielna bez reszty przez inną. Są one narzędziami pomocniczymi ułatwiającymi sprawdzenie czynników liczby bez uciekania się do dzielenia. Choć podobne reguły mogą być one ułożone dla dowolnej podstawy, to niżej zawarto tylko reguły dotyczące systemu dziesiętnego.Twierdzenie o rekurencji uniwersalnej jest twierdzeniem matematycznym pozwalającym w łatwy sposób znajdować ograniczenie asymptotyczne pewnej klasy funkcji zdefiniowanych rekurencyjnie.

    Jedną z typowych sytuacji, w których stosuje się rekurencję jest przeszukiwanie struktury danych w postaci nieregularnego drzewa, np. plików XML. Funkcja, która sprawdza czy w danym obiekcie XML istnieje element o określonej zawartości mogłaby wyglądać następująco (tutaj w PHP przy użyciu klasy SimpleXML):

    Funkcja rekurencyjna – funkcja N i → N {displaystyle mathbb {N} ^{i} ightarrow mathbb {N} } , która jest obliczalna za pomocą maszyny Turinga. Klasę tych funkcji definiuje się za pomocą mniejszej klasy funkcji pierwotnie rekurencyjnych:Programowanie dynamiczne jest techniką lub strategią projektowania algorytmów, stosowaną przeważnie do rozwiązywania zagadnień optymalizacyjnych. Jest alternatywą dla niektórych zagadnień rozwiązywanych za pomocą algorytmów zachłannych. Wynalazcą techniki jest amerykański matematyk Richard Bellman, uhonorowany za to odkrycie medalem IEEE (ang. medal of honour) w 1979 roku.
        function find_text($text, $tree) {
    
            // sprawdź zawartość aktualnego elementu
            if ($text == (string)$tree) {
                return true;
            }
    
            // sprawdź wszystkie jego dzieci
            foreach ($tree as $node) {
    
                // tutaj następuje wywołanie rekurencyjne
                if (find_text($text, $node)) {
                    return true;
                }
    
            }
    
            // nic nie znaleziono
            return false;
        }
    

    W językach, w których nie ma możliwości użycia rekurencji, a w których funkcje są typem pierwszoklasowym, istnieje możliwość dodania obsługi rekurencji poprzez kombinator Y. Przykładem może być rachunek lambda.

    Algorytm Euklidesa – pierwszy znany algorytm wyznaczania największego wspólnego dzielnika dwóch liczb naturalnych. Został opisany przez greckiego matematyka, Euklidesa w jego dziele "Elementy", w księgach siódmej oraz dziesiątej.Funkcja (łac. functio, -onis, „odbywanie, wykonywanie, czynność”) – dla danych dwóch zbiorów X i Y przyporządkowanie każdemu elementowi zbioru X dokładnie jednego elementu zbioru Y. Oznacza się ją na ogół f, g, h itd.

    Przykłady[ | edytuj kod]

  • algorytm Euklidesa
  • cecha podzielności przez 3 dla liczby w zapisie dziesiętnym
  • ciąg Fibonacciego
  • definicja silni
  • funkcja Ackermanna
  • wielomiany Czebyszewa
  • wielomiany Hermite’a
  • wielomiany Legendre’a
  • symbol Newtona
  • Zobacz też[ | edytuj kod]

  • derekursywacja
  • strategia typu dziel i zwyciężaj
  • efekt Droste
  • funkcja rekurencyjna
  • rekursja ogonowa (tail recursion)
  • rekursja pośrednia
  • równanie rekurencyjne
  • twierdzenie o rekurencji uniwersalnej
  • Linki zewnętrzne[ | edytuj kod]

  • Eric W. Weisstein, Recursion, [w:] MathWorld [online], Wolfram Research [dostęp 2020-12-12] (ang.).
  • Thomas Bolander, Self-Reference, [w:] Stanford Encyclopedia of Philosophy [online], CSLI, Stanford University, 31 sierpnia 2017, ISSN 1095-5054 [dostęp 2018-01-17] (ang.). (Samoodniesienie)

  • Programowanie funkcyjne (lub programowanie funkcjonalne) – filozofia i metodyka programowania będąca odmianą programowania deklaratywnego, w której funkcje należą do wartości podstawowych, a nacisk kładzie się na wartościowanie (często rekurencyjnych) funkcji, a nie na wykonywanie poleceń.Samopodobieństwo – w matematyce właściwość zbioru, przejawiająca się tym, że kształt całego zbioru jest podobny do kształtu fragmentu tego zbioru (jednego lub kilku). Wiele obiektów w świecie rzeczywistym, jak np. linia brzegowa, jest statystycznie samopodobnych: ich fragmenty przejawiają takie same statystyczne właściwości w wielu różnych skalach. Samopodobieństwo jest typową własnością fraktali.




    Warto wiedzieć że... beta

    Kontrola autorytatywna – w terminologii bibliotekoznawczej określenie procedur zapewniających utrzymanie w sposób konsekwentny haseł (nazw, ujednoliconych tytułów, tytułów serii i haseł przedmiotowych) w katalogach bibliotecznych przez zastosowanie wykazu autorytatywnego zwanego kartoteką wzorcową.
    International Standard Serial Number, ISSN czyli Międzynarodowy Znormalizowany Numer Wydawnictwa Ciągłego – ośmiocyfrowy niepowtarzalny identyfikator wydawnictw ciągłych tradycyjnych oraz elektronicznych. Jest on oparty na podobnej koncepcji jak identyfikator ISBN dla książek, ISAN dla materiałów audio-wideo. Niektóre publikacje wydawane w seriach mają przyporządkowany zarówno numer ISSN, jak i ISBN.
    Gemeinsame Normdatei (GND) – kartoteka wzorcowa, stanowiąca element centralnego katalogu Niemieckiej Biblioteki Narodowej (DNB), utrzymywanego wspólnie przez niemieckie i austriackie sieci biblioteczne.
    Największy wspólny dzielnik – dla danych dwóch (lub więcej) liczb całkowitych największa liczba naturalna dzieląca każdą z nich. Pojęcie to ma wiele uogólnień, które przedstawiono w dalszej części artykułu.
    Łacina, język łaciński (łac. lingua Latina, Latinus sermo) – język indoeuropejski z podgrupy latynofaliskiej języków italskich, wywodzący się z Lacjum (łac. Latium), krainy w starożytnej Italii, na północnym skraju której znajduje się Rzym.
    Efekt Droste to termin określający specjalny rodzaj rekurencyjnego obrazu. Obraz ukazujący efekt Droste zawiera mniejszą wersję samego siebie. Ta mniejsza wersja zawiera jeszcze mniejszą wersję w tym samym miejscu i tak dalej. Teoretycznie, może się to ciągnąć w nieskończoność, ale praktycznie jest to ograniczone rozdzielczością obrazu, czyli względnie krótko, gdyż każdy obraz jest zmniejszany wykładniczo.

    Reklama

    Czas generowania strony: 0.029 sek.