Funkcje rekurencyjne to takie, które wywoÅ‚ujÄ… same siebie, tylko zazwyczaj z innymi parametrami. Funkcje te mogÄ… dziaÅ‚ać ‘od koÅ„ca’, lub ‘od poczÄ…tku’.
Może najlepiej to wytÅ‚umaczyć na przykÅ‚adzie ćwiczenia ‘piramida’. W ćwiczeniu piramida trzeba wyÅ›wietlić piramidkÄ™ zÅ‚ożonÄ… na przykÅ‚ad z gwiazdek, ale wykorzystujÄ…c funkcjÄ™ rekurencyjnÄ…. Najpierw rozpatrzmy ten prostrzy przypadek, kiedy piramidka ma stać na suficie, czyli ma stać najkrótszÄ… krawÄ™dziÄ… do doÅ‚u. FunkcjÄ™ musimy wywoÅ‚ać z parametrem oznaczajÄ…cym wysokość tej piramidy, powiedzmy 5. Nagłówek tej funkcji bÄ™dzie wyglÄ…daÅ‚ tak:
void piramida(int level){
No więc na początku wyświetlamy ilość gwiazdek odpowiednią dla tego poziomu, czyli na początek 5, zwykłą pętlą for. No i dalej trzeba wyświetlać kolejne poziomy. Jak to robić? Wywołać funkcję piramida z poziomem o jeden mniejszym, czyli piramida(level - 1). No ale tak to by piramida wykonywała się w nieskończoność. Kiedy to ma przestać się wykonywać? Kiedy dojdziemy do pojedyńczej gwiazdki, czyli kiedy level jest równy jeden. Czyli przed wywołaniem piramidy z poziomem o jeden mniejszym trzeba wstawić odpowiedni warunek:
if(level > 1) piramida(--level);
Wtedy piramida skończy się rysować w odpowiednim momencie. Cała funkcja będzie wyglądała tak:
void piramida(int level){
for(int i = 0; i < level; i++)
System.out.print("*");
System.out.println();
if(level > 1)
piramida(level - 1);
}
Teraz wywołanie tej funkcji: piramida(5) wyświetli coś takiego:
***** **** *** ** *
Jak to działa? Najpierw wchodzimy w funkcję piramida(5), a więc na początku level jest równy 5. Pętla for wykonuje się 5 razy, rysuje się 5 gwiazdek. Sprawdzany jest warunek czy level jest większy od 1. No jest. No to wywołujemy funkcję piramida(4). I dalej to samo, 4 gwiazdki, wywołanie piramida(3) i tak aż do piramida(1), kiedy wyświetlana jest jedna gwiazdka, ostatni warunek nie jest spełniony i wszystko się kończy.
Teraz może trochę utrudnię zadanie. Jak zrobić, żeby ta piramida wyświetliła się w normalny sposób, czyli nie stała na suficie? W jakiś sposób, zaczynając od wywołania piramida(5) trzeba dojść do wywołania piramida(1) i dopiero wtedy zacząć rysować cofając się. Jak to wygląda w praktyce? Wywołanie samej siebie przez funkcję musi następować przed wyświetlaniem danych:
void piramida(int level){
if(level > 1)
piramida(level - 1);
for(int i = 0; i < level; i++)
System.out.print("*");
System.out.println();
}
i wyświetli się:
* ** *** **** *****
No więc teraz jak to działa? Najpierw ręcznie wywołujemy funkcję piramida(5). Java wchodzi w funkcję, sprawdza warunek, teraz jest spełniony, a więc wywoływana jest funkcja piramida(4) i tak dalej aż do piramida(1). Teraz warunek nie jest spełniony, więc program przechodzi dalej. Wyświetlana jest jedna gwiazdka. To wywołanie funkcji się kończy. No ale przecież jeszcze pozostałe 4 funkcje się nie skończyły - doszły tylko do wywołania samej siebie i w tym momencie kontrolę przejęło to następne wywołanie. Ale po dojściu do końca piramida(1), piramida(2) dalej czeka. No więc po wyjściu z funkcji piramida(1), Java powraca do funkcji piramida(2) w linii zaraz po tej, w której wywołuje samą siebie. No i dalej wyświetla 2 gwiazdki. Dochodzi do końca tego wywołania i wraca do piramida(3). Tam wyświetla 3 gwiazdki i wraca do piramida(4) i tak aż do wyświetlenia 5 gwiazdek i zakończeniu działania
funkcji.
Zasadniczo trudne to nie jest, tylko bardzo pomieszane. Trzeba pamiętać, że po funkcja po wywołaniu samej siebie, po skończeniu tego wywołania, wraca spowrotem miejsca, w którym wywoływała siebie (jeśli ktoś coś z tego zdania zrozumiał, to gratuluję). Bardzo to pomieszane, więc może kolejny przykład. Także z ćwiczeń, trójkąt Pascala. Jeśli ktoś nie wie, to trójkąt Pascala wygląda tak (dla 5 poziomów):
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
Ale teraz jak go wyliczyć? Już widać, że wyÅ›wietlanie ma być “od koÅ„ca”, bo najmniejsza wartość jest na górze. Tyle że sprawa jest trochÄ™ bardziej skomplikowana, bo do wyliczenia każdego wiersza oprócz poprzedniego potrzebny jest wynik z poprzedniego wiersza. Ja to zrobiÅ‚em tak, że funkcja jako parametr przekazuje caÅ‚Ä… tablicÄ™, częściowo wypeÅ‚nionÄ…. No i na samym koÅ„cu funkcja zwraca już caÅ‚Ä… wypeÅ‚nionÄ… tablicÄ™.
Pierwsze wywołanie będzie takie:
int[][] wynik = trojkat(5, null);
Dlaczego ‘null’ zamiast tablicy? Bo funkcja ma jÄ… sobie sama wypeÅ‚nić. Jej nagłówek bÄ™dzie taki:
int[][] trojkat(int level, int[][] table){
No wiÄ™c na poczÄ…tku trzeba jakoÅ› stworzyć tÄ… tablicÄ™. Jakiej ma być wielkoÅ›ci? Każdy wiersz bÄ™dzie innej dÅ‚ugoÅ›ci - pierwszy bÄ™dzie miaÅ‚ jeden element, drugi dwa itp. Ale wiadomo ile bÄ™dzie wierszy - tyle ile ma pierwszy ‘level’. Ale trzeba zrobić zabezpieczenie, żeby tabela tworzyÅ‚a siÄ™ za każdym razem, a tylko za pierwszym:
if(table==null){
table = new table[level][];
}
Robimy tylko ‘level’-wierszy. Kolumn jeszcze nie, bo dla każdego wiersza liczba kolumn bÄ™dzie inna. Jako że tablica ma być robiona od koÅ„ca, to w tym momencie trzeba zrobić wywoÅ‚anie rekurencji:
if(level>1) trojkat(level - 1, table)
Teraz można sobie spokojnie stworzyć wiersz w tablicy. Trzeba tylko pamiętać o numerowaniu wierszy. Poziom będzie na przykład piąty, ale indeksem wiersza w tablicy bedzie 4, czyli:
table[level - 1] = new int[level];
Miejsce w tablicy mamy już przygotowane. Pozostaje tylko pytanie jak jÄ… wypeÅ‚nić. Od razu widać, że pierwszym is ostatnim elementem tablicy jest 1, a wiÄ™c pierwsze 2 wiersze mamy zaÅ‚atwione samymi jednynkami. Ale jak to wyglÄ…da w pozostaÅ‚ych przypadkach? Chyba najÅ‚atwiej bÄ™dzie to zauważyć jeÅ›li ’spÅ‚aszczymy’ trójkÄ…t:
1 1 1 1 2 1 1 3 3 1 1 4 6 4 1
No i teraz można łatwo zauważyć, że każdy element (oprócz pierwszego i ostatniego) jest sumą tego elementu, który jest nad nim, i tego co jest nad nim po lewej. Jak to zapisać? Najpierw pętla:
for(int i = 0; i < level; i++){
Teraz trzeba sprawdzić, czy aktualnie sprawdzany nie jest przypadkiem elementem pierwszym lub ostatnim. Jeśli tak, to trzeba wstawić do niego jedynkę:
if(i == 0 || i == level - 1) table[level-1][i] = 1;
W przeciwnym przypadku trzeba zrobić to sumowanie o którym pisałem wyżej:
else table[level-1][i] = table[level-2][i] + table[level-2][i-1];
No i to w zasadzie rozwiązuje nam wszystko. Jak wygląda cała funkcja?
int[][] trojkat(int level, int[][] table){
if(table==null)
table = new int[level][];
if(level>1)
trojkat(level - 1, table);
table[level - 1] = new int[level];
for(int i = 0; i<level; i++){
if(i == 0 || i == level - 1)
table[level-1][i] = 1;
else
table[level-1][i] = table[level-2][i] + table[level-2][i-1];
}
return table;
}
Jak widać, wystarczy najpierw rozpoznać czy funkcja ma działać od końca czy od początku, pomyśleć czy niezbędne jest przekazywanie danych (czy, jak, ile), odpowiednio przeliczać to wszystko i na koniec w jakiś sposób zwrócić wynik końcowy.
Jeszcze jeden przykład rozwiązania zadania rekurencją znajduje się w opisie zadań z drugiego kolokwium.
Tags:
Zostaw komentarz