Metoda rekurencyjna – przypomnienie

Program będący zapisem metody rekurencyjnej ma postać funkcji, aby mógł odwoływać się do samego siebie. Każda funkcja rekurencyjna musi mieć warunek zakończenia rekurencji (zwany również warunkiem stopu) oraz przynajmniej jedno miejsce, w którym funkcja wywołuje samą siebie.

Kiedy ostatnie wywołanie funkcji kończy swoją pracę, również funkcja, która je spowodowała, może zakończyć swoje działanie. Proces ten powtarza się dla każdego wywołania funkcji, aż pierwsze w kolejności wywołanie funkcji zwróci wartość będącą wynikiem działania rekurencji.

W następstwie wywołania funkcji zostaje ona odłożona na szczyt stosu (charakterystyka tej struktury danych znajduje się w e‑materiale Podstawowe struktury danych: stos i kolejkaPE9Hyf0CXPodstawowe struktury danych: stos i kolejka), natomiast kiedy zakończy ona swoje działanie, jest ze stosu zdejmowana.

Prześledźmy, jak wygląda metoda rekurencyjna i proces tworzenia stosu z jej wykonania.

public class Main {
    public static int potega(int a, int n){
        if (n == 1) return a;
        return a * potega(a, n - 1);
    }

    public static void main (String [] args) {
        potega(2,3);
    }
}

Najpierw wywołana zostaje metoda main, która jako pierwsza zostaje odłożona na stosie. Następnie wywołujemy metodę potega(2, 3), a po niej metodę potega(2, 2). Jako ostatnia wywołana zostaje metoda potega(2, 1), w której napotkany jest warunek zakończenia rekurencji.

R1FUe0e1Uzf14

Grafika przedstawia proces tworzenia stosu metodą rekurencyjną. Widoczne są trzy stosy w kształcie odwróconej drabinki. W pierwszej drabince od lewej strony u podstawy jest napis main. W drugiej drabince u podstawy napis mein i poziom wyżej napis potęga a w nawiasie okrągłym liczby dwa przecinek trzy. W trzej drabince u podstawy napis main. Poziom wyżej napis potęga i w nawiasie okrągłym liczby dwa przecinek trzy. Poziom wyżej napis potęga w nawiasie okrągłym liczby dwa przecinek dwa. Poziom wyżej napis potęga w nawiasie okrągłym liczby dwa przecinek jeden.

Gdy wywołanie metody potega(2, 1) zakończy swoje działanie, zostaje ono zdjęte ze stosu, następnie przetwarzane jest wywołanie metody potega(2, 2), które także jest zdejmowane ze stosu, ponieważ zwróciło swój wynik, analogiczna operacja zajdzie dla wywołania metody potega(2, 3).

Ryqo1OpuigLyD

Grafika przedstawia proces zdejmowania ze stosu. Widoczne są trzy stosy w kształcie odwróconej drabinki. W pierwszej drabince od lewej u podstawy jest napis main. Poziom wyżej napis potęga w nawiasie okrągłym liczby dwa przecinek trzy. Poziom wyżej napis potęga w nawiasie okrągłym liczby dwa przecinek dwa. Poziom wyżej napis potęga w nawiasie okrągłym liczby dwa przecinek jeden. W drugiej drabince u podstawy jest napis main. Poziom wyżej napis potęga w nawiasie okrągłym liczby dwa przecinek trzy. Poziom wyżej napis potęga w nawiasie okrągłym liczby dwa przecinek dwa. W trzeciej drabince u podstawy jest napis main. Poziom wyżej napis potęga w nawiasie okrągłym liczby dwa przecinek trzy.

Kiedy liczba wywołań rekurencyjnych będzie stale rosła, np. z powodu nieumieszczenia w metodzie warunku zakończenia rekurencji, może dojść do przepełnienia stosuprzepełnienie stosuprzepełnienia stosu (o czym poinformuje komunikat: Exception in thread "main" java.lang.StackOverflowError).

Jest to błąd w programowaniu polegający na zapełnieniu się roboczego obszaru pamięci operacyjnej programu wywołaniami funkcji oraz ich lokalnymi zmiennymi. Stos ma określoną pojemność, gdy zostanie przepełniony, nowe zmienne zostają umieszczone poza nim, co prowadzi do błędów. Tak wyglądałoby przepełnienie stosu dla metody potega(2, 3), w której nie umieszczono warunku zakończenia rekurencji.

RZl9I1JfkkYse

Grafika przedstawia proces przepełnienia stosu z powodu braku warunku zakończenia rekurencji. . Widoczne są trzy stosy w kształcie odwróconej drabinki. W pierwszej drabince od lewej strony u podstawy jest napis main. W drugiej drabince u podstawy napis mein i poziom wyżej napis potęga a w nawiasie okrągłym liczby dwa przecinek trzy. Poziom wyżej napis potęga. W nawiasie okrągłym liczby dwa przecinek dwa. Poziom wyżej napis potęga. W nawiasie okrągłym liczby dwa przecinek jeden. W trzej drabince u podstawy napis main. Poziom wyżej napis potęga i w nawiasie okrągłym liczby dwa przecinek trzy. Poziom wyżej napis potęga w nawiasie okrągłym liczby dwa przecinek dwa. Poziom wyżej napis potęga w nawiasie okrągłym liczby dwa przecinek jeden. mein . Poziom wyżej napis potęga a w nawiasie okrągłym liczby dwa przecinek zero. Poziom wyżej napis potęga. W nawiasie okrągłym liczby dwa przecinek minus jeden. Na szczycie trzej drabinki widoczny jest napis. Otrzymasz komunikat o przepełnieniu stosu. Exception in thread w cudzysłów main cudzysłów java kropka long kropka Stacoverflowerror.

Metoda iteracyjna – przypomnienie

Metoda iteracyjna opiera się na powtarzaniu tej samej operacji w pętli. Pętli for używamy, gdy wiemy, ile iteracji pętli jest potrzebnych do rozwiązania problemu. Natomiast pętlę while wykorzystamy, gdy nie będziemy umieli określić, ile iteracji należy wykonać w celu rozwiązania problemu. Istnieje jeszcze pętla do while, której działanie jest podobne do pętli while, różni się jednak tym, że warunek pętli sprawdzany jest dopiero po wykonaniu każdej iteracji.

Porównanie metod

Główne różnice między metodami rekurencyjną i iteracyjną to szybkość oraz sposób działania, a także – łączące się z nimi – wymagania dotyczące zasobów komputera.

W większości przypadków algorytmy rekurencyjne są mniej efektywne pamięciowo niż ich iteracyjne wersje. Różnica jest spowodowana tym, że metoda rekurencyjna wielokrotnie odwołuje się do samej siebie. Każde rekurencyjne wywołanie funkcji ma swoje własne zmienne, ponieważ wywoływana jest nowa funkcja. Każde wywołanie funkcji zajmuje pewien obszar pamięci. Problem pojawia się wówczas, gdy tworzone jest kolejne wywołanie, a nie zostało zakończone poprzednie, a tak właśnie się dzieje przy wykorzystaniu rekurencji. Nie jest to zauważalne w przypadku mniej skomplikowanych programów, w których wywołań rekurencyjnych jest niewiele. Jednak jeśli problem jest bardziej wymagający, wykorzystanie pamięci rośnie. W momencie, gdy nieumiejętnie zastosujemy rekurencję, może dojść do przepełnienia stosu i pojawienia się komunikatu: Exception in thread "main" java.lang.StackOverflowError. Zaletą zastosowania algorytmu rekurencyjnego jest przejrzystość oraz czytelność kodu.

Częstym błędem, przez który rekurencyjne wersje algorytmów działają wolniej niż ich iteracyjne odpowiedniki, są nieoptymalnie skonstruowane wywołania. Jest tak w wypadku algorytmu, w którym funkcja kilka razy liczy to samo, np. algorytmu rekurencyjnego wyznaczającego elementy ciągu Fibonacciego.

Warto wiedzieć, kiedy należy użyć metody rekurencyjnej, a kiedy lepiej pozostać przy iteracyjnej. Rekurencja często ułatwia zrozumienie i rozwiązanie problemu, jeśli faktycznie jest to zgodne z jego charakterem.

Dobrym przykładem odstępstwa metody iteracyjnej w kwestii tworzenia algorytmów jest problem potęgowania. Standardową definicję potęgowania możemy zapisać następująco:

Zaprezentowana definicja nie posiada żadnej istotnej zalety względem wersji iteracyjnej. Można powiedzieć, że utrudnia zrozumienie natury problemu. Dodatkowo jej implementacja wprowadza sporo niewystępujących w przypadku wersji iteracyjnej problemów, związanych na przykład z przepełnieniem stosu.

Implementacja potęgowania liczb

Aby omówić różnice programistyczne w przypadku różnych podejść do problemu, porównajmy przykładowe implementacje metod realizujących definicje matematyczne w języku Java. Zacznijmy od potęgowania liczb.

Specyfikacja problemu:

Dane:

• a – liczba naturalna; podstawa potęgi

• n – liczba całkowita; wykładnik potęgi

Wynik:

Program zwraca wartość zmiennej a podniesionej do potęgi n.

Wersja iteracyjna:

public static int potegowanieIteracyjnie(int a, int n) {
    int wynik = a;
    for (int i = 1; i < n; ++i) {
        wynik *= a;
    }

    return wynik;
}

Wersja rekurencyjna:

public static int potegowanieRekurencyjnie(int a, int n) {
    if (n == 1) return a;
    return a * potegowanieRekurencyjnie(a, n - 1);
}

Widoczna na pierwszy rzut oka różnica, która przemawia na korzyść rozwiązania rekurencyjnego, to długość kodu. Zauważmy, że zapis metody potegowanieRekurencyjnie() jest krótszy. W wielu algorytmach funkcje rekurencyjne są prostsze i krótsze w zapisie.

Porównywanie długości kodu to często jednak błąd. Liczba linijek kodu jest mniej ważna od jego wydajności. Przeanalizujmy zatem aspekty wydajnościowe obu rozwiązań. Złożoność czasowa obu funkcji jest taka sama. Inaczej sprawa ma się w przypadku złożoności pamięciowej. W wersji iteracyjnej, aby obliczyć wartość funkcji dla danego parametru n, deklarujemy tylko cztery zmienne. W przypadku funkcji napisanej rekurencyjnie liczba zmiennych jest znacząco zwiększona. Przy obliczaniu wartości potęgi dla danego parametru n, będziemy mieli liczbę zmiennych rzędu $2·n$, ponieważ dla każdego rekurencyjnego wywołania funkcji tworzymy dwie zmienne lokalne a i n.

Niepotrzebnie zwiększone jest zatem zapotrzebowanie na pamięć na stosie, co może powodować niemożliwość wykonania funkcji dla dużych parametrów n. W przypadku operacji potęgowania mamy do czynienia z bardzo szybkim wzrostem wyniku. Prawdopodobnie nie doświadczymy w tym wypadku problemu z przepełnieniem stosu, gdyż i tak podniesienie liczby do odpowiednio dużej potęgi byłoby niemożliwe z uwagi na pojemność zmiennej typu int czy nawet long. Inaczej byłoby w przypadku próby obliczenia następującego działania:

Uzyskanie wyniku przedstawionej operacji byłoby niemożliwe do osiągnięcia z pomocą podejścia rekurencyjnego zbudowanego w sposób analogiczny do zdefiniowanej wcześniej funkcji. W tym wypadku trzeba zastosować podejście iteracyjne lub algorytm tzw. szybkiego potęgowania (w wersji zarówno iteracyjnej, jak i rekurencyjnej).

Implementacja silni matematycznej

Porównajmy teraz dwie wersje algorytmu obliczającego silnię matematyczną zapisane w języku Java.

Silnia to jednoargumentowa funkcja matematyczna, której wynikiem jest iloczyn wszystkich liczb naturalnych (oprócz zera) nie większych niż argument silni.

Rozpiszmy przykładową postać algorytmów. Zaczniemy od metody iteracyjnej.

Specyfikacja problemu:

Dane:

• n – liczba całkowita; argument silni

Wynik:

Program zwraca wartość silni n.

public class Main {
    public static int silniaIteracyjna(int n){
        int wynik = 1;

        while(n > 0) {
            wynik = wynik * n;
            n--;
        }
        return wynik;

    }
    public static void main (String [] args) {
       System.out.print(silniaIteracyjna(5));
    }

}

Zmienna n przechowuje argument metody silnia, w tym przypadku jest to $5$, więc matematyczna reprezentacja problemu wygląda następująco: $5!$

Specjalnym przykładem silni jest liczba $0!$, gdyż jako wynik zwraca ona $1$. Dlatego do zmiennej wynik przypisywana jest wartość $1$. W pętli najpierw sprawdzany jest warunek czy $n>0$. Pozwala to na mnożenie zmiennej wynik przez kolejne wartości $n$. Po zakończeniu pętli wynik działania $5!$ zostaje zwrócony z metody silniaIteracyjna, a następnie wypisany w konsoli.

W przypadku rekurencyjnej wersji problemu, kod wygląda następująco:

public class Main {
    public static int silniaRekurencyjna(int n) {
        if (n == 0) return 1;
        return n * silniaRekurencyjna(n - 1);
    }

    public static void main (String [] args) {
       System.out.print(silniaRekurencyjna(5));
    }

}

Ponownie rozważamy przypadek specjalny dla $0!$, więc gdy n = 0 zwracamy wartość $1$. Gdy n jest różne od $0$, wywołujemy metodę silniaRekurencyjna(n‑1) oraz mnożymy ją razy n.

Rekurencyjne powielanie obliczeń

Wspomnieliśmy już o tym, że nieumiejętna implementacja funkcji rekurencyjnej może skutkować zwiększoną liczbą wykonanych operacji. Zagadnienie to dobrze obrazuje problem obliczania n-tego wyrazu ciągu Fibonacciego, kod w języku Java reprezentujący rekurencyjne rozwiązanie problemu wygląda następująco:

public class Main{
    public static int fib(int n){ //rekursywnie
        //warunki zakończenia
        if(n == 0) return 0;
        if(n == 1) return 1;
		//wywołanie rekurencyjne
        return  fib(n - 2) + fib(n - 1);
    }

    public static void main (String [] args) {
        System.out.println(fib(8));
    }
}

Dla wywołania metody fib(8) otrzymamy następujące drzewo wywołań rekurencyjnych:

R1Bn6c4XEkhdU

Grafika przedstawia drzewo wywołań rekurencyjnych. U szczytu drzewa napis fib w nawiasie okrągłym sześć. Od napisu odchodzą dwie gałęzie, w lewą i prawą stronę. Po lewej stronie linia prowadzi do napisu fib w nawiasie okrągłym pięć. Po prawej stronie linia prowadzi do napisu fib w nawiasie okrągłym fib cztery. Od tych napisów odchodzą kolejne dwie gałęzie, w lewą i prawą stronę. Odpowiednio: fib w nawiasie okrągłym cztery, fib nawiasie okrągłym trzy, fib nawiasie okrągłym trzy, fib nawiasie okrągłym dwa. Od fib w nawiasie okrągłym cztery odchodzą kolejne dwie gałęzie fib w nawiasie okrągłym trzy i fib w nawiasie okrągłym dwa. Od fib w nawiasie okrągłym cztery odchodzą kolejne dwie gałęzie fib w nawiasie okrągłym trzy i fib w nawiasie okrągłym dwa. Od fib w nawiasie okrągłym trzy odchodzą kolejne dwie gałęzie fib w nawiasie okrągłym dwa i fib w nawiasie okrągłym jeden. Od fib w nawiasie okrągłym trzy odchodzą kolejne dwie gałęzie fib w nawiasie okrągłym dwa i fib w nawiasie okrągłym jeden. Od fib w nawiasie okrągłym dwa odchodzą kolejne dwie gałęzie fib w nawiasie okrągłym jeden i fib w nawiasie okrągłym zero. Od fib w nawiasie okrągłym trzy odchodzą kolejne dwie gałęzie fib w nawiasie okrągłym dwa i fib w nawiasie okrągłym jeden. Od fib w nawiasie okrągłym dwa odchodzą kolejne dwie gałęzie fib w nawiasie okrągłym jeden i fib w nawiasie okrągłym zero. Od fib w nawiasie okrągłym dwa odchodzą kolejne dwie gałęzie fib w nawiasie okrągłym jeden i fib w nawiasie okrągłym zero. Od fib w nawiasie okrągłym dwa odchodzą kolejne dwie gałęzie fib w nawiasie okrągłym jeden i fib w nawiasie okrągłym zero. Od fib w nawiasie okrągłym dwa odchodzą kolejne dwie gałęzie fib w nawiasie okrągłym jeden i fib w nawiasie okrągłym zero. Od fib w nawiasie okrągłym dwa odchodzą kolejne dwie gałęzie fib w nawiasie okrągłym jeden i fib w nawiasie okrągłym zero. Od fib w nawiasie okrągłym jeden i fib w nawiasie okrągłym zero nie odchodzą już żadne gałęzie.

Na grafice kolorami zaznaczone są wielokrotne wywołania metody fib(6), fib(5), fib(4) itd. Przez nieumiejętne użycie rekurencji wielokrotnie obliczamy wartości identycznych wywołań metody, co powoduje ogromny wzrost zajmowanej pamięci na stosie.

Na przytoczonym przykładzie możemy zauważyć, że używanie rekurencji może czasem prowadzić do niepotrzebnego powielania obliczeń, w przypadku tego problemu opłaca się zastosować metodę iteracyjną.

public class Main{
    public static int fib(int n){ //iteracyjnie
        int a = 1; //pierwszy i drugi wyraz
        int b = 1; //ciągu Fibbonaciego
        int wyraz = 1; //wartość bierzącego wyrazu ciągu
        
        for(int i = 3; i <= n; i++){ //pierwsze 2 wyrazy
            wyraz = a + b;           // są już obliczone
            a = b;
            b = wyraz;
        }
        return wyraz;
    }

    public static void main (String [] args) {
        System.out.println(fib(1));
    }
}

Dzięki metodzie iteracyjnej używamy tylko $4$ zmiennych, a także nie powielamy obliczeń.

Słownik