Rekurencja (rekursja) w Javie

by Red 26 października 2020

Java podobnie jak wiele innych języków programowania pozwala na używanie rekurencji. Oznacza to, że metoda może wywołać sama siebie. To co działa względnie prosto na kartce nie zawsze jest takie proste do zaimplementowania w aplikacji. W tym artykule postaramy się przybliżyć pojęcie rekurencji oraz pokazać kiedy warto pokusić się o jej zastosowanie we własnych programach.

Czym jest rekurencja?

Rekurencja zwana też rekursją jest sposobem definiowania algorytmów w taki sposób, żeby odwoływał się do siebie wielokrotnie aż zostanie spełniony warunek wyjścia. Jest to najważniejszy punkt, gdyż w przeciwnym wypadku taka procedura wykonywałaby się bez końca. Dokładniej do momentu aż skończą się zasoby i dostaniemy nieprzyjemny komunikat o przepełnieniu stosu.

Inną kwestią jest stos wywołań rekurencyjnych gdyż zbyt duży może potrzebować ogromnych ilości pamięci operacyjnej lub negatywnie wpłynąć na złożoność obliczeniową.

Rekurencja w Javie

Przykład rekurencji pokażemy implementując algorytm podnoszenia liczby m do potęgi n. Oczywiście w celu przejrzystości nie przejmujemy się nieprawidłowymi danymi i zakładamy, że użytkownik zawsze podaje liczby całkowite większe niż 0.

public class Potegowanie {
public static void main(String[] args)  {
System.out.print(pow(2,3));
}
public static int pow(int m, int n) {
if(n==1)
return m;
return pow(m, n-1)*m;
}
}

public class Potegowanie {

public static void main(String[] args) {

System.out.print(pow(2,3));

}

public static int pow(int m, int n) {

if(n==1)

return m;

return pow(m, n-1)*m;

}

Wynikiem tego wywołania będzie liczba 8.

Przyjrzyjmy się teraz metodzie pow. Zgodnie z definicją potęgowania argument m mnożymy przez siebie n razy. Korzystając z rekurencji możemy wykorzystać fakt, że 2³ = 2*2². W ogólności m^n = m*m^n-1. Zatem przed wywołaniem tej reguły ustalamy warunek końcowy. Czyli w przypadku gdy wartość n jest równa 1, to zwracamy m. Formalnie moglibyśmy napisać, że jest to m¹.

Rozwiązując problem algorytmem iteracyjnym moglibyśmy użyć pętli for jak poniżej.

public int pow(int m, int n) {
int res = 1;
for (int i=0;i<n; i++) {
res *=m;
}
return res;
}

public int pow(int m, int n) {

int res = 1;

for (int i=0;i<n; i++) {

res *=m;

}

return res;

}

Zalety i wady rekurencji

Niektóre problemy można w bardzo prosty oraz intuicyjny sposób rozwiązać lub zapisać przy pomocy rekurencji. Najlepszym chyba przykładem jest zapis ciągu Fibonacciego. Jego definicją jest następująca. Pierwszy wyraz ciągu jest równy 0, a drugi 1. Każdy wyraz ciągu dla n > 2 jest sumą dwóch poprzednich. Intuicyjnie jest zatem napisać formę rekurencyjnie.

F(n) = F(n-1) + F(n-2), dla n > 2

F(0) = 0

F(1) = 1

Kod w Javie ciągu Fibonacciego wygląda następująco.

public class Fibonacci{
public static void main(String[] args)  {
System.out.println(fibonacci(12));
}
public static int fibonacci(int n) {
if(n == 0) {
return 0;
}else if(n== 1){
return 1;
}else {
return fibonacci(n-1) + fibonacci(n-2);
}
}
}

public class Fibonacci{

public static void main(String[] args) {

System.out.println(fibonacci(12));

}

public static int fibonacci(int n) {

if(n == 0) {

return 0;

}else if(n== 1){

return 1;

}else {

return fibonacci(n-1) + fibonacci(n-2);

}

Takie rozwiązanie problemu jest bardzo intuicyjne. Jednakże nie jest ono pozbawione wad. Największą jest podwójne wywołanie samej siebie. Każde pojedyncze wywołanie powoduje dwa kolejne. Zatem obliczenie 5 wyrazu ciągu potrzebuje 2⁴ wywołań.

Zwróćmy również uwagę na obliczanie danej wartości dwukrotnie. Poniżej pokażemy w postaci drzewa obliczenie <n> wyrazu ciągu. Ze względu na czytelność wykresu pominęliśmy powstawanie wyrazu o wartości 1.

Ciąg Fibonacciego rekurencja

Jak widać na powyższym obrazku im wyższy poziom drzewa, tym więcej razy obliczany jest ten sam wyraz ciągu. Tej wady można uniknąć stosując iteracyjny algorytm jednakże jest on mniej przejrzysty i wymaga dodatkowej zmiennej.

Metody rekurencyjne nie muszą zwracać żadnej wartości – mogą być typu void.

Innym przydatnym może być algorytm wyszukiwania elementów w drzewach bst.

public Wezel getWezel(Wezel node, int key) {
if (key > node.getKey()){
return getWezel(node.getRight(), key);
}else if(key < node.getKey()) {
return getWezel(node.getLeft(), key);
}else {
return node;
}
}