Rekurencja - cóż to takiego?
Cały świat jawi nam się jako zbiór fraktalifraktali. Nie znajdujemy w nim idealnych geometrycznych kształtów, takich jak koła, prostokąty, sześciany, stożki, które moglibyśmy obliczyć przy pomocy prostych wzorów matematycznych.
Czy istnieje metoda, by zmierzyć coś tak nieregularnego jak fraktale? Czy umiemy odzwierciedlić matematycznie te skomplikowane kształty?
Istnieje rozwiązanie, które jest odpowiedzią na te pytania i brzmi: równania rekurencyjnerekurencyjne.
Rekurencja
RekurencjaRekurencja w informatyce oznacza program, który odwołuje się sam do siebie. Aby zastosować rekurencję w programowaniu, musimy wiedzieć, jak ją zdefiniować. Robimy to w dwóch krokach:
Pierwszy krok polega na określeniu przypadku bazowego, czyli najprostszego przypadku, dla którego rozwiązanie jest znane i nie wymaga kolejnych wywołań funkcji.
Drugi krok polega na określeniu kroku rekurencyjnego, czyli reguły, według której funkcja odwołuje się do samej siebie, rozwiązując problem dla mniejszych danych lub prostszego przypadku. Dane muszą być tak przekształcane, aby kolejne wywołania prowadziły do przypadku bazowego.
Podobnie działa rekurencja – rozwiązanie problemu polega na wielokrotnym stosowaniu tej samej reguły do coraz prostszych przypadków. Ważne jest określenie przypadku bazowego oraz takiej reguły, która doprowadzi do niego po skończonej liczbie kroków.
Wszystkie algorytmy rekurencyjne muszą być zbudowane z kolejnych kroków:
mają określony warunek początkowy (który mówi nam, kiedy zadanie jest ukończone i należy ukończyć pracę);
przeprowadzają działania w celu wypełnienia warunku początkowego;
stosują rekurencję, czyli odwołują się do samych siebie.
Fraktale
Dzięki stosowaniu rekurencji możemy konstruować fraktalefraktale, ponieważ jesteśmy w stanie rozwiązać problem w oparciu o rozwiązania tego samego problemu dla danych o mniejszym rozmiarze.
FraktaleFraktale są bardzo złożonymi figurami geometrycznymi, których nie możemy zaliczyć ani do brył, ani do krzywych, ani do powierzchni. Nad fraktalami pracowano już na początku XX wieku, ale dopiero powstanie komputerów pozwoliło na ich badanie. Wielu badaczy twierdzi, że fraktale ukazują geometrię przyrody.
Fraktale mogą być definiowane jako obiekty o strukturze powstającej w wyniku wielokrotnego powtarzania określonej operacji matematycznej. W wielu przypadkach proces ten można kontynuować w nieskończoność. Rysunki fraktali tworzone za pomocą komputera przedstawiają jednak tylko skończoną liczbę etapów konstrukcji, czyli przybliżenia tych obiektów. Do ich tworzenia można wykorzystać algorytmy rekurencyjne.
Fraktale posiadają odmienne cechy niż znane nam dotąd figury geometryczne:
mogą być opisywane za pomocą wzorów matematycznych lub iterowanych reguł, a do ich konstruowania można wykorzystywać algorytmy rekurencyjne;
wiele fraktali ma wymiar niecałkowity, ale nie jest to cecha wszystkich fraktali;
ich strukturę można badać na coraz mniejszych skalach, a kolejne etapy konstrukcji pozwalają uzyskiwać coraz dokładniejsze przybliżenia .
Notatnik
Film edukacyjny
Prezentacja multimedialna
Zapoznaj się z prezentacją i odpowiedz na pytanie, dlaczego uważa się, że świat naturalny ma budowę fraktalną. Wymień przykłady trzech rzeczy w naturze, które charakteryzują się taką budową i uzasadnij swoją odpowiedź.
Film dostępny pod adresem /preview/resource/RnAIpShz39gos
Filmik przedstawia zbliżenie na sześciany, które składają się z mniejszych sześcianów, złożonych z sześcianów.
Przedstaw w szkicowniku sposób tworzenia zbioru Cantora.
Przedstaw własnymi słowami, na czym polega samopodobieństwo fraktali.
Zestaw ćwiczeń interaktywnych
Co oznacza rekurencja w programowaniu? Możliwe odpowiedzi: 1. Rekurencja w programowaniu oznacza taki program, który odwołuje się sam do siebie., 2. Rekurencja w programowaniu oznacza taki program, który działa w nieskończoność., 3. Rekurencja w programowaniu oznacza taki program, który jest zbudowany z wielu różnych algorytmów.
Która z postaci w 1883 roku przedstawiła swój pomysł opisu najprostszego fraktala?
Które z poniższych cech charakteryzują fraktale? Możliwe odpowiedzi: 1. skończoność figur, 2. możliwość tworzenia przy pomocy algorytmów rekurencyjnych, 3. wymiar, który nie jest liczbą całkowitą, 4. niemożliwość przeprowadzenia transformacji części figury
Opisz własnymi słowami, jaki związek ma rekurencja z fraktalami.
Wymyśl problem, który mógłby zostać opisany przy pomocy rekurencji i przedstaw kolejne kroki zmierzające do rozwiązania go.
Słownik
(łac. fractus – złamany, cząstkowy, ułamkowy) obiekt samopodobny, czyli taki, którego części są podobne do całości, oznacza to, że część fraktala wygląda podobnie do całego obiektu, niezależnie od powiększenia; fraktale często mają złożone i nieregularne kształty, które powtarzają się w coraz mniejszych szczegółach; są one stosowane w matematyce, naukach przyrodniczych, grafice komputerowej i sztuce
właściwość figur, która polega na tym, że jej części są podobne do całości
jeden z najbardziej znanych fraktali; tworzony poprzez podział równobocznego trójkąta na cztery mniejsze równoboczne trójkąty, a następnie powtarzanie tych kroków dla każdego z tych trójkątów; tworzą się w ten sposób coraz mniejsze kopie trójkąta początkowego
(ang. recursion, z łac. recurrere, przybiec z powrotem) inaczej rekursja; w matematyce i w informatyce (np. w programowaniu) działanie polegające na odwoływaniu się do samego siebie, np. do własnej definicji, funkcji lub procedury
dający się przedstawić za pomocą już znanych wielkości; np. wzór rekurencyjny – można obliczyć wyrazy ciągu na podstawie jednego lub kilku wyrazów, które były już w tym ciągu użyte