• 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ń).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).
      dla 

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

    PHP – obiektowy język programowania zaprojektowany do generowania stron internetowych i budowania aplikacji webowych w czasie rzeczywistym.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:

    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:

    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.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ą".
    1. dla     oznacza tu resztę z dzielenia przez

    lub inaczej:

    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.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.

    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.

    Twierdzenie o rekurencji uniwersalnej jest twierdzeniem matematycznym pozwalającym w łatwy sposób znajdować ograniczenie asymptotyczne pewnej klasy funkcji zdefiniowanych rekurencyjnie.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.

    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ą.

    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.

    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):

    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ń.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.
        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;
        }
    

    Przykłady[ | edytuj kod]

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

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

  • 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)
  • 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.



    w oparciu o Wikipedię (licencja GFDL, CC-BY-SA 3.0, autorzy, historia, edycja)

    Warto wiedzieć że... beta

    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.