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 prostszy 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 pojedynczej 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.
