Fraktale — samopodobieństwo na ekranie

🎯 Po co Ci to?

Do tej pory rekurencja była abstrakcją — łańcuchem wywołań, drzewem na papierze. Teraz zobaczysz ją na własne oczy. Fraktale to figury, które zawierają własne pomniejszone kopie — nieskończenie głęboko. Narysowanie ich pętlą byłoby koszmarem; rekurencją to kilka linijek, bo kod fraktala jest definicją fraktala. To najpiękniejsze spotkanie z rekurencją w całej informatyce — i jedyne, w którym efekt Twojej pracy można powiesić na ścianie. Wszystkie cztery fraktale z tej jednostki są wprost wymienione w rozszerzonej podstawie.

✅ Czego się nauczysz

Po tej jednostce potrafisz:

  • opisać rekurencyjną konstrukcję czterech klasycznych fraktali (Cantor, drzewo, Sierpiński, Koch);
  • zapisać taką konstrukcję jako funkcję rekurencyjną z głębokością jako parametrem;
  • wyjaśnić rolę przypadku bazowego (głębokość 0) jako „dna" rysowania.

🔁 Przypomnij sobie

Z 7.1: baza + krok; z 7.2: rozgałęzienie (fraktale wołają siebie kilka razy — jak Fibonacci, ale tu rozgałęzienie jest celem, bo tworzy kopie).

📘 Wyjaśnienie

Wszystkie fraktale rekurencyjne mają tę samą strukturę: narysuj kształt, a potem narysuj jego mniejsze kopie w wybranych miejscach — chyba że osiągnąłeś zadaną głębokość (baza), wtedy przestań. Głębokość jest parametrem: to ona zamienia „nieskończony" fraktal matematyczny w rysowalny obiekt skończony.

Zbiór Cantora — najprostszy. Weź odcinek. Usuń środkową trzecią. Zostają dwa odcinki — z każdym zrób to samo. I tak w głąb:

głębokość 0:  ████████████████████████████
głębokość 1:  █████████        █████████
głębokość 2:  ███   ███        ███   ███
głębokość 3:  █ █   █ █        █ █   █ █

def cantor(x, dlugosc, glebokosc):
    if glebokosc == 0:               # baza: nie dziel dalej
        return
    narysuj_odcinek(x, dlugosc)      # narysuj bieżący odcinek
    cantor(x, dlugosc/3, glebokosc-1)                    # lewa trzecia
    cantor(x + 2*dlugosc/3, dlugosc/3, glebokosc-1)      # prawa trzecia

Dwa wywołania rekurencyjne = dwie kopie. Rozgałęzienie, które u Fibonacciego było przekleństwem, tutaj jest istotą — bo podproblemy są rozłączne (lewa i prawa trzecia to różne miejsca) i każdy naprawdę trzeba narysować.

zbiór Cantoradrzewo binarnetrójkąt Sierpińskiegopłatek Kocha (fragment)
Cztery klasyczne fraktale rekurencyjne: zbiór Cantora (odcinki dzielone na trzy), drzewo binarne (pień rozgałęziający się na dwie mniejsze gałęzie), trójkąt Sierpińskiego (trójkąt z trzema mniejszymi w rogach) i płatek Kocha (bok zastępowany łamaną z ząbkiem). · rys. własny

Drzewo binarne — pień, a na jego końcu dwie mniejsze, obrócone gałęzie; z każdą to samo. Baza: gałąź za krótka (albo głębokość 0) — nie rozgałęziaj. Trzy linijki rekurencji tworzą coś łudząco podobnego do prawdziwego drzewa — bo prawdziwe drzewa rosną dokładnie tak: powtarzając ten sam wzorzec rozgałęzienia w coraz mniejszej skali. Rekurencja to nie tylko technika programistyczna; to sposób, w jaki natura buduje złożoność z prostej reguły.

Trójkąt Sierpińskiego (nasz, polski — Wacław Sierpiński, 1915!) — trójkąt, w którym środkowy (odwrócony) wycinamy, a z trzema narożnymi robimy to samo. Płatek Kocha — każdy bok odcinka zastępujemy łamaną z trójkątnym ząbkiem, i tak z każdym nowym bokiem; efekt to nieskończenie „poszarpana" linia skończonej średnicy.

💭 Pomyśl: W funkcji cantor co się stanie, jeśli usuniesz przypadek bazowy if glebokosc == 0: return? A co, jeśli zostawisz bazę, ale zapomnisz narysuj_odcinek?

Sprawdź odpowiedź

Bez bazy: rekurencja schodzi w nieskończoność (odcinki coraz krótsze, ale głębokość nigdy nie spada do zera) → RecursionError. Matematyczny Cantor JEST nieskończony — ale komputer musi mieć dno, i tym dnem jest głębokość. Bez narysuj_odcinek: rekurencja przebiega poprawnie, dochodzi do bazy… i nie rysuje nic — bo cała robota rysowania była w pominiętej linijce. Program działa, ekran pusty. To rozróżnienie jest sednem: rekurencja steruje, ale rysuje zwykła instrukcja — pomyl role, a albo się zapętlisz, albo dostaniesz pustkę.

🤯 Ciekawostka

Fraktale to nie tylko matematyczna zabawa. Benoît Mandelbrot, który ukuł termin „fraktal" w 1975 roku, zauważył, że linia brzegowa ma naturę fraktalną: im dokładniej mierzysz, tym dłuższa wychodzi (każda zatoczka ma mniejsze zatoczki). Stąd słynne pytanie „jak długie jest wybrzeże Wielkiej Brytanii?" — odpowiedź brzmi: zależy od długości linijki, i rośnie bez granic, gdy linijka maleje. Fraktalne algorytmy generują dziś góry i chmury w filmach, modelują naczynia krwionośne i sieci rzeczne, a kompresja fraktalna ściska obrazy — wszystko z jednej idei: skomplikowany kształt z prostej, powtarzanej reguły.

🛠️ Teraz Ty

Bez komputera: narysuj ręcznie zbiór Cantora do głębokości 4 i trójkąt Sierpińskiego do głębokości 2 (na papierze w trójkąty, jeśli masz). Z komputerem: jeśli masz dostęp do biblioteki rysującej (w Pythonie moduł turtle jest wprost stworzony do fraktali — „żółw" rysuje, obraca się, a rekurencja steruje), zaimplementuj drzewo binarne: def galaz(dlugosc, glebokosc) rysuje odcinek, obraca żółwia w lewo, woła siebie z krótszą gałęzią, obraca w prawo, woła znów. Pobaw się głębokością i kątem — zobacz, jak z jednej reguły rodzi się las.

📐 Definicje tej lekcji

  • Fraktal — figura zawierająca własne pomniejszone kopie (samopodobna); rekurencyjnie: kształt + mniejsze kopie siebie, aż do głębokości bazowej.
  • Głębokość — parametr ucinający nieskończoną konstrukcję do rysowalnej; przypadek bazowy rekurencji.

📌 Najważniejsze w pigułce

  • Kod fraktala = jego definicja: narysuj kształt, potem mniejsze kopie, chyba że głębokość 0.
  • Rozgałęzienie rekurencji tworzy tu kopie — to cel, nie wada (podproblemy rozłączne, każdy potrzebny).
  • Głębokość zamienia nieskończony fraktal matematyczny w skończony obraz; baza to jej wyczerpanie.

🎒 Zadania

  1. Ile odcinków ma zbiór Cantora na głębokości $k$? A ile trójkącików (pełnych) ma Sierpiński na głębokości $k$?
Wskazówka i odpowiedź

Cantor: każdy odcinek rodzi 2 — więc na głębokości $k$ jest $2^k$ odcinków (0→1, 1→2, 2→4, 3→8…). Sierpiński: każdy trójkąt rodzi 3 — $3^k$ trójkącików. Liczba kopii rośnie wykładniczo z głębokością — dlatego głębokość 20 to już milion odcinków Cantora, a rysowanie zwalnia. Wykładniczy wzrost, tym razem widoczny gołym okiem jako gęstniejący rysunek.

  1. Napisz (pseudokodem lub w Pythonie) rekurencyjną funkcję rysującą zbiór Cantora, jawnie zaznaczając bazę i dwa wywołania. Co przekazujesz w każdym wywołaniu?
Wskazówka i odpowiedź

Jak w 📘: baza glebokosc == 0, potem narysuj_odcinek(x, dlugosc), potem dwa wywołania z jedną trzecią długości i głębokością o jeden mniejszą — lewe od x, prawe od x + 2*dlugosc/3. Kluczowe: w obu wywołaniach dlugosc/3 (kopie są trzy razy mniejsze) i glebokosc-1 (schodzimy ku bazie). Pomyl któreś — albo kopie nie zmaleją, albo rekurencja nie dojdzie do dna. Parametry rekurencji kodują geometrię fraktala.

  1. Płatek Kocha startuje z odcinka i na każdym poziomie zastępuje każdy bok czterema krótszymi (z ząbkiem). Ile boków ma po $k$ poziomach, jeśli start to 1 bok? Jak rośnie długość całej linii?
Wskazówka i odpowiedź

Boków: $4^k$ (każdy rodzi cztery). Długość: każdy nowy bok ma $1/3$ długości starego, ale jest ich 4 — więc długość na poziom mnoży się przez $4/3$: po $k$ poziomach to $(4/3)^k$ początkowej. Rośnie bez granic ($(4/3)^k \to \infty$), choć płatek mieści się w skończonym obszarze! Nieskończona linia w skończonym pudełku — to właśnie fraktalny paradoks wybrzeża z ciekawostki, policzony. Matematyka rekurencji potrafi zaskoczyć nawet po policzeniu.

🔍 Sprawdź, czy umiesz

  • Opisać rekurencyjną konstrukcję każdego z czterech fraktali (kształt + kopie + baza).
  • Wskazać w kodzie fraktala, co steruje (rekurencja) i co rysuje (instrukcja).
  • Policzyć, jak liczba kopii i długość rosną z głębokością.

Ucz się tej jednostki z asystentem