PROCEDURY REKURENCYJNE

1. WPROWADZENIE
   •  CO TO JEST REKURENCJA? 
2. PROSTE REKURENCJE
   •  SPIRALA 
   •  KWADRATY 
3. RYSOWANIE FRAKTALI
   •  PŁATEK KOCHA 
   •  DRZEWO BINARNE 
   •  PLASTER MIODU 
   •  TRÓJKĄT SIERPIŃSKIEGO 

Motto:

Co to jest rekurencja?

Rekurencja jest to wywołanie podporgramu (procedury) samej przez siebie. W logo zapis rekurencji będzie wyglądał następująco:

? oto nazwa_funkcji
? czynności_wykonywane_przez_procedurę
? nazwa_funkcji
? już

Zauważ, że tak skonstruowana procedura działałaby w nieskończoność. Dlateg przygotowojąc funkcję rekurencyjną zawsze musisz zadbać o istnienie parametru warunkującego kolejne wykonanie procedury. Skorzystaj w tym celu z procedury warunkowej jeśli. Ma ona następującą strukturę:

jeśli warunek [co_zrobić_gdy_prawda] [co_zrobić_gdy_fałsz]

A oto dwa przykłady:

? oto nazwa_funkcji :parametr
? jeśli :parametr = 0 [stop]
? czynności_wykonywane_przez_procedurę
? nazwa_funkcji :parametr - 1
? już

? oto nazwa_funkcji :parametr
? czynności_wykonywane_przez_procedurę
? jeśli :parametr > 10 [nazwa_funkcji :parametr / 2]
? już

Jak działają powyższe funkcje?

W pierwszym wypadku procedura zostanie wykonana w zależności od wielkośći parametru [dokładnie tyle razy ile wynosi wartość :parametr].

W drugim wypadku procedura będzie wykonywana nieokreśloną ilość razy do momentu, gdy wartość parametru spadnie poniżej założonej wielkości (w naszym wypadku 10).

Spróbujmy zatem coś narysować.

Spirala

Najprostrzym przykładem rekurencji będzie dla Ciebie narysowanie spirali. Jak powstaje spirala? Spróbuj narysować ją poprzez poruszanie się żółwiem do przodu za każdym razem zmniejszając krok o 2 punkty aż do wielkości kroku 5. Za każdym razem obracaj żółwia o 90 stopni w prawo. Procedurę i wynik możesz obejżeć poniżej.

? oto spirala :bok
? jeśli :bok < 10 [stop]
? np :bok pw 90
? spirala :bok - 2
? już

Spróbuj zdefiniować podobną procedurę. Dodaj jednak parametr określający kąt obrotu żółwia zamiast jednostajnego 90 stopni. Procedurę oraz wyniki jej wywołania możesz zobaczyć poniżej.

? oto spirala :bok :kąt
? jeśli :bok < 10 [stop]
? np :bok pw 90
? spirala :bok - 2 :kąt
? już

spirala 200 122	spirala 200 135

Kwadraty

Zobacz, jak łatwo za pomocą rekurencji narysować kilka kolenych kwadratów.

Aby narysować taki obrazek za pomocą zwykłej procedury z parametrem, musiałbyś ją wywaoływać dziecięc razy! Zastąpisz ją jedną procedurą rekurencyjną. Po proctu za każdym razem będziesz zmniejszał wielkość boku o 20 aż uzyskasz wartość mniejszą niż 10.

? oto kwadraty :bok
? jeśli :bok < 10 [stop]
? powtórz 4 [np :bok pw 90]
? kwadraty :bok - 20
? już

Spróbuj teraz narysować piramidę z kwadratów. Napisz procedurę piramida :n, która wywołana z parametrem narysuje piramidę o n rzędach, przy czym w pierwszym rzędzie będzie n kwadratów, natomiast w każdym kolejnym rzędzie będzie stopniowo o jeden kwadrat mniej. Przykładowo, w wyniku wywołania piramida 4 otrzymasz figurę przedstawioną na poniższym rysunku:

Jak to działa? Najpierw musisz narysować kwadrat i ustawić się do rysowania kolejnego kwadratu. Czynność tę 4 powtarzasz razy.

W tym celu musisz wykonać następujące polecenia:

powtórz :n [powtórz 4 [np 50 pw 90] pw 90 np 50 lw 90]

Następnie wracasz do punktu początkowego:

pw 90 ws :n * 50 lw 90

Teraz ustawiasz się na miejscu rysowania kolejnej warstwy piramidy:

np 50 pw 90 np 25 lw 90

Nie pozostało Ci nic innego, niż wywołać całą procedurę rekurencyjnie:

piramida :n - 1

A oto i cała treśc procedury. Nie zapominaj o warunku przerwania pętli!

? oto piramida :n
? jeśli :n = 0 [stop]
? powtórz :n [powtórz 4 [np 50 pw 90] pw 90 np 50 lw 90]
? pw 90 ws :n * 50 lw 90 np 50 pw 90 np 25 lw 90
? piramida :n - 1
? już

Fraktale to, najprościej ujmując, wielokrotnie powtarzane motywy w postaci krzywych. Charakteryzują się tym, że ich części składowe są pomniejszonym obrazem całości.

Płatek Kocha

Najprostrzym fraktalem jest płatek Kocha. Jako stopień zerowy tego fraktala przymujemy odcinek o długości :n (wywołanie koch 0 100).

Stopień pierwszy powstaje przez podział odcinka na trzy równe części, a następnie zastąpienie środkowej części dwoma złączonymi odcinkami równymi części usuniętej (wywołanie koch 1 100).

Aby utworzyć stopień drugi, musisz podzielić każdy z odcinków na 4 nowe (wywołanie koch 2 100).

Tak będzie się prezentować się wywołanie koch 4 100.

A oto procedura, która pozwoli Ci narysować pojedyńczy płatek:

oto koch :stopień :długość
 jeśli :stopień = 0 [np :długość stop]
 koch :stopień - 1 :długość / 3 pw 60
 koch :stopień - 1 :długość / 3 lw 120
 koch :stopień - 1 :długość / 3 pw 60
 koch :stopień - 1 :długość / 3
już

Pełny płatek Kocha będziesz mógł zobaczyć trzykrotnie powtarzając rysowanie pojednczego "listka".

oto gwiazdka :stopień :długość
 powtórz 3 [koch :stopień :długość lw 120]
już

Wynik wywołania gwiazdka 4 150.

Drzewo binarne

To także przykład bardzo prostego fraktala. Jak go otrzymasz? Musisz narysować kreskę, na jej końcu dwie kolejne kreski położone względem siebie pod kątem 45^o, na ich końcach kolejne dwie kreski...

oto dbin :wiek :pien
 jeśli :wiek = 0 [np :pien pw 180 np :pien stop]
 np :pien
 lw 45
 dbin :wiek - 1 :pien * 0,6
 lw 90
 dbin :wiek - 1 :pien * 0,6
 lw 45
 np :pien
już

dbin 0 50

dbin 1 50

dbin 2 50

dbin 3 50

dbin 6 50

Plaster miodu

Ten fraktal otrzymasz rysując sześcian, a następnie rysując sześć mniejszych sześcianów na początku każdego boku, potem rysujesz sześcian na boku każdego z małych sześcianów...

oto plaster :poziom :bok
 jeśli :poziom = 0 [stop]
 powtórz 6 [np :bok plaster :poziom - 1 :bok / 2 pw 60]
już

plaster 1 50

plaster 2 50

plaster 3 50

plaster 4 50

Trójkąt Sierpińskiego

Ten fraktal otrzymasz rysując trójkąt.

sierpinski 0 150

Kolejna czynność to narysowanie wewnątrz następnego trójkąta o boku równym połowie pierwszego.

sierpinski 1 150

Następnie wrysowujesz wewnątrz trzech trójkątów podobnych kolejny trójkąt.

sierpinski 2 150

Można tak jeszcze długo..

sierpinski 5 150

oto troj :a
 powtórz 3 [np :a pw 120]
już

oto sierp :n :a
 jeśli :n = 0 [troj :a stop]
 troj :a
 sierp :n - 1 :a / 2
 np :a / 2
 sierp :n - 1 :a / 2
 pw 60
 np :a / 2 pw 60
 sierp :n - 1 :a / 2
 lw 60 ws :a / 2
 lw 60 ws :a / 2
już

oto sierpinski :n :a
 cs
 pw 30
 sierp :n :a
już