--------------------------------------------------------------- Oznaczenia: !Rys.n! - rysunek numer n Uwaga! W listingach TAB=3 ------------------------------------------------------------ AMOS -- REKURENCJA Niewiele osób wie, ûe AMOS umoûliwia wykorzystanie tzw. rekurencji. Czym jest rekurencja, czy warto z niej korzystaê, a jeûeli tak, to w jaki sposób? Krzysztof Prusik Krzywa Przypuôêmy, ûe chcemy narysowaê fragment krzywej, stycznej do dwóch prostych, zadanych punktami A, B, C (rys. 1.). Jak to zrobiê? ---------!Rys.1!------------------ Chyba wszyscy wiemy, ûe komputerowe krzywe, "tak naprawdë" nie sâ krzywymi, lecz liniami îamanymi, zîoûonymi z duûej liczby odcinków (rys. 2.). ----------!Rys.2!------------------ Îatwo zauwaûyê, ûe im wiëcej odcinków, tym dokîadniejszy rysunek, czyli bardziej "wygîadzona krzywa". Chcâc zrealizowaê zadanie, jakie sobie postawiliômy na poczâtku artykuîu, powinniômy znaleúê dostatecznie duûo punktów (P1, P2, P3, P4...) leûâcych na naszej krzywej i poîâczyê je odcinkami. Proste, prawda? Tylko jak znaleúê te punkty? Krok 1.: Dzielimy na póî odcinki AB i BC, w wyniku czego otrzymujemy nowe punkty D i E. Dzielimy na póî odcinek DE, w wyniku czego otrzymujemy punkt F. Krok 2.: Dzielimy na póî odcinki AD, DF, FE i EC, w wyniku czego otrzymujemy punkty G, H, I, J. Dzielimy na póî GH i IJ, otrzymujemy K i L. Krok 3., 4., 5. itd. -- wedîug powyûszego schematu. Krok ostatni: Îâczymy punkty odcinkami, wedîug porzâdku: punkt A, kolejne otrzymane w ostatnim kroku punkty, punkt C. ----------------!Rys.3!---------------------- Czy jasne jest, ûe postëpujâc w ten sposób, otrzymujemy w kolejnych krokach coraz dokîadniejszâ krzywâ? Tak? No to bierzemy sië do kodowania. Ha! Problem niby rozwiâzany, ale jak napisaê program? Z pomocâ przychodzi rekurencja. Oto rozwiâzanie problemu przy jej wykorzystaniu. Piszemy procedurë OBLICZ[X1,Y1,X2,Y2,X3,Y3], która dla zadanych punktów A(X1,Y1), B(X2,Y2), C(X3,Y3) wyliczy ôrodki odcinków AB i BC, czyli D(X4,Y4) i E(X5,Y5), oraz ôrodek DE, czyli F(X6,Y6), a nastëpnie wywoîa procedury OBLICZ[X1,Y1,X4,Y4,X6,Y6] i OBLICZ[X6,Y6,X5,Y5,X3,Y3]. Proponujë Ci, ûebyô sië teraz nad tym chwilë zastanowiî, bo to jest wîaônie "gwóúdú programu". Czy juû mniej wiëcej "jarzysz" o co biega? No to "lecim dalej"! Procedura OBLICZ bëdzie w "nieskoïczonoôê" wywoîywaîa samâ siebie, bez przerwy dzielâc na póî wszystkie odcinki, jakie napotka na swojej drodze. Musimy przyznaê, ûe poza maîâ niedogodnoôciâ, jakâ jest "nieskoïczone obliczenie", nasza procedura bardzo skutecznie wyznacza wspóîrzëdne punktów, leûâce na krzywej. Co wiëc zrobiê, aby OBLICZ w pewnym momencie przestaîo sië wywoîywaê rekurencyjnie "w gîâb"? Ano moûna np. spowodowaê, aby procedura wywoîywaîa samâ siebie tylko wtedy, gdy odlegîoôci miëdzy punktami sâ wiëksze niû _DOKÎADNOÔÊ (nowa staîa, przechowujâca dîugoôê odcinka, dla którego rysowana linia îamana bëdzie juû przypominaê krzywâ). OK? No to, koderzy! Do kodowania! ' Krzywa (C) 1994 By Arni Fusik ' Program rysuje krzywâ stycznâ do dwóch prostych '-------------------------------- ekran w duûej rozdzielczoôci Screen Open 0,640,512,2,Hires+Laced '-------------------------------- dokîadnoôê krzywej do kwadratu _DOKLADNOSC=1 Global _DOKLADNOSC '-------------------------------- punkt A(X1,Y1) X1=0 Y1=Screen Height-1 '-------------------------------- punkt B(X2,Y2) X2=(Screen Width-1)/2 Y2=0 '-------------------------------- punkt C(X3,Y3) X3=Screen Width-1 Y3=Screen Height-1 '-------------------------------- rysujemy krzywâ KRZYWA[X1,Y1,X2,Y2,X3,Y3] ' Procedure KRZYWA[X1,Y1,X2,Y2,X3,Y3] '----------------------------------------------- ' procedura rysuje krzywâ, stycznâ do prostej, ' przechodzâcej przez punkty: ' A(X1,Y1) i B(X2,Y2) ' oraz stycznâ do prostej, przechodzacej przez: ' B(X2,Y2) i C(X3,Y3) '----------------------------------------------- ' ---- wykreôl pierwszy punkt Plot X1,Y1 OBLICZ[X1,Y1,X2,Y2,X3,Y3] End Proc Procedure OBLICZ[X1,Y1,X2,Y2,X3,Y3] '--------------------------------------------------------- ' Parametrami wejôciowymi sâ wspóîrzëdne punktów: ' A(X1,Y1); B(X2,Y2); C(X3,Y3); ' ' Procedura dzieli odcinki AB i BC na póî. Powstajâ ' nowe punkty D(X4,Y4) i E(X5,Y5). Nastëpnie prodedura ' dzieli odcinek DE na póî, a nowo otrzymany punkt F(X6,Y6) ' wykorzystuje do tego, aby rekurencyjnie wykonaê ' OBLICZ(A,D,F) i OBLICZ(F,E,C) '--------------------------------------------------------- ' ---- odlegîoôê miëdzy punktami A(X1,Y1) i B(X2,Y2) ODLEGLOSC=Sqr((X2-X1)*(X2-X1)+(Y2-Y1)*(Y2-Y1)) ' ---- czy wymagana dokîadnoôê juû jest? If ODLEGLOSC<=_DOKLADNOSC ' ---- jeûeli tak, to juû rysujemy Draw To X3,Y3 ' ---- i nie wywoîujemy OBLICZ dalej "w gîâb" Else ' ---- w przeciwnym wypadku: ' ---- obliczamy wspóîrzëdne punktu D(X4,Y4) X4=(X1+X2)/2 Y4=(Y1+Y2)/2 ' ---- analogicznie obliczamy punkt E(X5,Y5) X5=(X2+X3)/2 Y5=(Y2+Y3)/2 ' ---- a nastëpnie F(X6,Y6) X6=(X4+X5)/2 Y6=(Y4+Y5)/2 ' ---- póúniej rekurencyjnie, wykonujemy: OBLICZ[X1,Y1,X4,Y4,X6,Y6] OBLICZ[X6,Y6,X5,Y5,X3,Y3] End If End Proc Czy wszystko jasne? Jeûeli tak, to uruchom program i sprawdú efekt jego dziaîania na monitorze. Tak, wiem, dokîadnoôê pozostawia trochë do ûyczenia. Jej sîaba jakoôê spowodowana jest tym, ûe operujemy na liczbach caîkowitych, a nie rzeczywistych (przykîad dziaîania prowadzâcego do nieznacznego bîëdu: X1=3/2, czyli X1=1). Zadanie dla ambitnych: napisaê program, który rysuje krzywe jak na rysunku 3. ----------------!Rys.3!---------------------- Silnia A teraz, skoro juû wszyscy wiemy, ûe rekurencja czasami moûe byê bardzo pomocna, nowa wskazówka. Rekurencjë moûna wykorzystywaê nie tylko w bardzo skomplikowanych zadaniach, ale takûe w prostych, jak np. obliczanie silni. Program nie wykorzystujâcy rekurencji: ' Silnia (C) 1994 By Arni Fusik ' Program liczy silnie Repeat Print Input " Podaj wartoôê N : ";N SILNIA[N] Print " Silnia z N wynosi: ";Param Until N<=0 '------------------ procedura liczâca silnië z N Procedure SILNIA[N] WYNIK=1 If N>2 For I=2 To N WYNIK=WYNIK*I Next End If End Proc[WYNIK] Procedura rekurencyjna: Procedure SILNIA[N] If N=0 WYNIK=1 Else SILNIA[N-1] WYNIK=N*Param End If End Proc[WYNIK] Czy widaê, ûe program z wykorzystaniem rekurencji jest prostszy od tego, który jej nie wykorzystuje? Zwróê uwagë na to, ûe procedura rekurencyjna ôciôle odpowiada definicji silni, znanej z lekcji matematyki: Jeûeli n=0, to n!=1 jeûeli n>0, to n!=n(n-1)! Fraktal A teraz nowe zadanie. Stwórzmy fraktal -- krzywâ trójkâtnâ. Wiadomo, ûe wyglâda on tak, jak na rysunku 4. -----------------!Rys.4!------------------- Jego rekurencyjna definicja jest nastëpujâca: Mamy trójkât ABC. 1. Dzielimy jego boki na poîowy, po czym otrzymane punkty îâczymy odcinkami. 2. Z kaûdym z trzech otrzymanych trójkâtów postëpujemy wedîug punktu 1. Listing programu: ' Fraktal (C) 1994 By Arni Fusik ' Program rysuje krzywâ trójkâtnâ '-------------------------------- ekran w duûej rozdzielczoôci Screen Open 0,640,512,2,Hires+Laced '-------------------------------- dokîadnoôê fraktala _DOKLADNOSC=10 Global _DOKLADNOSC '-------------------- punkt A X1=0 Y1=Screen Height-1 '-------------------- punkt B X2=(Screen Width-1)/2 Y2=0 '-------------------- punkt C X3=Screen Width-1 Y3=Screen Height-1 '-------------------- wywoîanie procedury rekurencyjnej TROJKAT[X1,Y1,X2,Y2,X3,Y3] Wait Key ' Procedure TROJKAT[X1,Y1,X2,Y2,X3,Y3] '--------------------- rysujemy nasz trójkât Plot X1,Y1 Draw To X2,Y2 Draw To X3,Y3 Draw To X1,Y1 '-------------------- czy wymagana dokîadnoôê juû jest? If X3-X1>_DOKLADNOSC '----------------- punkt D X4=X1+(X2-X1)/2 Y4=Y2+(Y1-Y2)/2 '----------------- punkt E X5=X2+(X3-X2)/2 Y5=Y2+(Y3-Y2)/2 '----------------- punkt F X6=X1+(X3-X1)/2 Y6=Y1+(Y3-Y1)/2 '----------------- wywoîujemy "w gîâb" TROJKAT[X1,Y1,X4,Y4,X6,Y6] TROJKAT[X6,Y6,X5,Y5,X3,Y3] TROJKAT[X4,Y4,X2,Y2,X5,Y5] End If End Proc A to juû ostatnia wskazówka. Gdy po wykonaniu programu, ze smutkiem stwierdzimy, ûe wystâpiî bîâd: Out of stack space to zamiast sië martwiê, moûemy na poczâtku programu dodaê instrukcjë: Set Stack ROZMIAR gdzie: ROZMIAR to wielkoôê stosu (w duûym przybliûeniu: maksymalna liczba rekurencyjnych wywoîaï procedury "w gîâb"). I to juû wszystko na dzisiaj. Czy zrozumiaîeô rekurencjë? Jeûeli uwaûasz, ûe ostatnie artykuîy sâ dla Ciebie zbyt trudne, to napisz do redakcji MA. W przeciwnym zaô wypadku, czyli jeûeli dotychczasowa forma artykuîów Ci odpowiada,... teû napisz. Do nastëpnego razu! Dla zainteresowanych: autor tego artykuîu korzysta z AMOS Professional v2.0, tak wiëc programy zamieszczane w Magazynie AMIGA sâ testowane za pomocâ tej wersji AMOS-a.