Na czym polega rekurencja?

Istotą rekurencjirekurencjarekurencji jest wykorzystanie funkcji, która – aby rozwiązać pewien problem – wywołuje samą siebie, aż do momentu, gdy zadanie zostanie wykonane. Funkcja ta może być typu voidfunkcja typu voidvoid, gdy wywoływana funkcja nie zwraca wartości do funkcji wywołującej, lecz np. wypisuje ją do konsoli. Najczęściej jednak funkcja rekurencyjna oblicza oraz zwraca wartość.

Aby mechanizm rekurencji działał poprawnie, potrzebny jest przynajmniej jeden warunek, po spełnieniu którego funkcja nie zostanie wywołana po raz kolejny, lecz zakończy działanie (a także zwróci wartość – o ile miała ją zwracać). Jeżeli taki warunek się nie pojawi, funkcja będzie wywoływać się w nieskończoność – może to spowodować zawieszenie programu – jak w przypadku nieskończonej pętlinieskończona pętlanieskończonej pętli – lub przepełnienie stosu. Nie otrzymamy wówczas rozwiązania problemu.

Z każdym kolejnym wywołaniem funkcji rekurencyjnej przynajmniej jeden z jej argumentówargument funkcjiargumentów musi zmienić wartość. Zmiany argumentów muszą prowadzić do przypadku bazowego. Wartości argumentów nie mogą powtórzyć się w następnych wywołaniach, z wyjątkiem argumentów, których wartości przerywają dany ciąg wywołań rekurencyjnych. Wartości argumentów stanowią wtedy przypadek podstawowy rekurencji. Jeżeli złamiemy chociaż jedną z przedstawionych zasad, funkcja rekurencyjna będzie wywoływać się bez końca. Kolejne wywołanie zostaje zapisane na stosie, więc gdy funkcja będzie uruchamiana w nieskończoność, w pewnym momencie stos przepełni się, a program zakończy działanie.

Każde rekurencyjne wywołanie funkcji zatrzymuje wykonywanie funkcji bieżącej. Czeka ona, aż funkcja przez nią wywołana zakończy działanie i zwróci wartość. Przy wywoływaniu kolejnych funkcji rekurencyjnych poprzednie funkcje także zatrzymują się i czekają, aż funkcje przez nie wywołane zwrócą obliczoną wartość.

Opisany proces można przedstawić graficznie przy użyciu drzewa wywołań rekurencyjnych.

R8UR63QhQDMVT

Drzewo wywołań rekurencyjnych.
Strzałkami o kolorze niebieskim oznaczono kolejne wywołania funkcja, a strzałkami o kolorze czerwonym zwrot wartości.
Funkcja(a), 1: Niebieska, Funkcja(b), 2: Niebieska, Funkcja(c), 3: Czerwona, Funkcja(b), 4: Niebieska, Funkcja(d), 5: Czerwona, Funkcja(b), 6: Czerwona, Funkcja(a), 7: Niebieska, Funkcja(e), 8: Niebieska, Funkcja(f), 9: Niebieska, Funkcja(g), 10: Czerwona, Funkcja(f), 11: Czerwona, Funkcja(e), 12: Czerwona, Funkcja(a).

Z przedstawionej grafiki wynika, że pierwszym wywołaniem funkcji rekurencyjnej Funkcja było: Funkcja(a). Ta z kolei w pierwszej kolejności wywołała rekurencyjnie Funkcja(b). A zatem wywołanie Funkcja(a) czeka, aż wywołana Funkcja(b) zwróci wartość.

Kolejnym krokiem było wywołanie Funkcja(c). Wywołanie funkcji z takim argumentem nie spowodowało kolejnego wywołania rekurencyjnego, lecz zwrócenie wartości. Zobrazowane to zostało przy użyciu czerwonej strzałki z oznaczeniem 3. Jednak Funkcja(b) wywołała nie jedno, lecz dwa wykonania rekurencyjne. Drugim jest Funkcja(d), które podobnie jak Funkcja(c), zamiast wywoływać dalsze wykonania rekurencyjne, zwróciła wartość.

Kolejny krok przedstawia czerwona strzałka z numerem 6. Wywołanie Funkcja(b) zwraca wartość do Funkcja(a). Następnym krokiem jest wywołanie kolejno: Funkcja(e) → Funkcja(f) → Funkcja(g), po czym ostatnie wywołanie zwraca wartość do poprzedniego i w ten sposób dochodzimy do pierwszego wywołania Funkcja(a), które finalnie zwraca wartość.

Rekurencja – przykład

Zanim przejdziemy do ciągu Fibonacciego, napiszmy prosty program wykorzystujący mechanizm rekurencji. Program ten zwróci sumę wszystkich liczb naturalnych mniejszych lub równych liczbie podanej jako argument.

Rozpoczynamy od zdeklarowania funkcji.

public static int sumaLiczbNaturalnych(int n) {
    
}

Ponieważ funkcja ma obliczyć sumę liczb naturalnych, typem zwracanych danych jest int. Parametr n będzie górną granicą składników sumy.

Zaczniemy od zapisania warunku, po spełnieniu którego funkcja zakończy działanie i zwróci wartość. Warunek będzie dotyczył najmniejszej możliwej wartości parametru n. Zakładamy, że liczby naturalne zaczynają się od 1. Ile wynosi suma liczb naturalnych mniejszych lub równych 1? Jest to 1. Skonstruujmy więc instrukcję warunkowąinstrukcja warunkowainstrukcję warunkową, która będzie odpowiedzialna za działanie programu w przypadku, gdy wartość n wynosi 1:

public static int sumaLiczbNaturalnych(int n) {
	if (n == 1) {
		return 1;
	}
}

Kolejnym i ostatnim krokiem jest rekurencyjne wywołanie funkcji.

public static int sumaLiczbNaturalnych(int n) {
	if (n == 1) {
		return 1;
	}
    
	return n + sumaLiczbNaturalnych(n - 1);
}

Ponieważ chcemy uzyskać sumę liczb naturalnych, a różnica między kolejnymi liczbami naturalnymi zawsze wynosi 1, za każdym razem, gdy wywołujemy kolejną funkcję, odejmujemy od jej argumentu wartość 1. Do wyniku tego wywołania dodajemy wartość aktualnego argumentu i ta suma zostaje przekazana funkcji, która wywołała bieżącą funkcję.

Aby lepiej zrozumieć działanie programu, sprawdźmy, jak się on zachowa, gdy jako argument podamy wartość 3.

public static int sumaLiczbNaturalnych(int n) {
	// n = 3
    
	if (3 == 1) {
		return 1;
	}
    
	return 3 + sumaLiczbNaturalnych(2);
}

Sprawdzamy, czy 3 jest równe 1. Nie jest to prawdą, więc pomijamy instrukcję warunkową i przechodzimy do wywołania rekurencyjnego. Liczbę 3 dodajemy do wartości zwróconej przez sumaLiczbNaturalnych(2). Funkcja przerywa działanie i przechodzi do funkcji, którą sama wywołała, czyli sumaLiczbNaturalnych(2).

public static int sumaLiczbNaturalnych(int n) {
	// n = 2
    
	if (2 == 1) {
		return 1;
	}
    
	return 2 + sumaLiczbNaturalnych(1);
}

Jak wiemy, 2 również nie jest równe 1. Pomijamy warunek i ponownie zatrzymujemy wykonywanie tej funkcji. Zwróćmy uwagę na funkcję, która została wywołana, czyli sumaLiczbNaturalnych(1).

public static int sumaLiczbNaturalnych(int n) {
	// n = 1
    
	if (1 == 1) {
		return 1;
	}
}

W tym przypadku instrukcja warunkowa nie zostanie pominięta. Skoro 1 == 1, nie wywołujemy już funkcji sumaLiczbNaturalnych(), lecz zwracamy wartość 1. Przekazujemy ją funkcji, która wywołała bieżącą funkcję.

public static int sumaLiczbNaturalnych(int n) {
	// n = 2
    
	if (2 == 1) {
		return 1;
	}
    
	return 2 + 1;
}

Ta z kolei otrzymała wartość, na którą czekała. Może więc dodać ją do swojego argumentu i zwrócić obliczony wynik funkcji, która wywołała tę wartość.

public static int sumaLiczbNaturalnych(int n) {
	// n = 3
    
	if (3 == 1) {
		return 1;
	}
    
	return 3 + 3;
}

Wywołana pierwotnie funkcja zwraca wartość 6, która jest sumą wszystkich liczb naturalnych mniejszych lub równych 3.

Ciąg Fibonacciego

Definicja ciągu Fibonacciego wygląda następująco: początkowymi elementami ciągu są 0 oraz 1, natomiast każdy kolejny element jest sumą dwóch poprzednich. Trzecim elementem ciągu Fibonacciego będzie zatem $0 + 1 = 1$, czwartym $1 + 1 = 2$, piątym $1 + 2 = 3$ itd. Indeksy elementów zaczynają się od 0, podobnie jak indeksy tablicy w języku Java. Pierwszy element – o wartości 0 – ma indeks n = 0.

Rekurencja

Iteracja

Napiszemy program, który zwróci element ciągu Fibonacciego o indeksie n. Zastosujemy iterację. Zaczniemy ponownie od utworzenia funkcji.

public static long iterFibonacci(int n) {

}

Wybieramy typ long, ponieważ wartości kolejnych wyrazów ciągu Fibonacciego rosną wykładniczo.

Parametr n funkcji będzie indeksem elementu ciągu, który ma być obliczony.

Zapisujemy warunki, po których spełnieniu zostanie zatrzymane działanie funkcji i zwróci ona wartość. Wiemy, że pierwszy wyraz ciągu Fibonacciego – zatem wyraz o indeksie 0 – ma wartość 0. Natomiast drugi wyraz – czyli wyraz o indeksie 1 – wynosi 1. Zapiszemy odpowiednie instrukcje warunkowe.

public static long iterFibonacci(int n) {
	if (n == 0) {
		return 0;
	} else if (n == 1) {
		return 1;
	}
}

Musimy brać również pod uwagę przypadek, gdy wartość parametru n jest większa niż 1. W takiej sytuacji każdy kolejny element jest sumą dwóch poprzednich. Dla dalszego działania funkcji potrzebujemy zmiennych pomocniczych. Inicjalizujemy trzy zmienne pomocnicze: a, b (oznaczające wartości dwóch początkowych wyrazów ciągu) oraz i (indeks kolejnego elementu ciągu Fibonacciego). Przypisujemy im odpowiednio wartości 0, 1 i 2.

public static long iterFibonacci(int n) {
	if (n == 0) {
		return 0;
	} else if (n == 1) {
		return 1;
	}
        
long a = 0;
long b = 1;
int i = 2;

}

Zapisujemy pętlę while, która będzie wykonywać się tak długo, dopóki wartość zmiennej i jest mniejsza od wartości zmiennej n lub jej równa.

public static long iterFibonacci(int n) {
	if (n == 0) {
		return 0;
	} else if (n == 1) {
		return 1;
	}
        
long a = 0;
long b = 1;
int i = 2;
    
while (i <= n) {
    
	}    
    
}

W każdym obiegu pętli while najpierw obliczamy i-ty wyraz ciągu, czyli sumę dwóch poprzednich wyrazów ciągu. Wynik przypisujemy do zmiennej suma. Następnie zmiennej a przypisujemy wartość zmiennej b, a zmiennej b wartość zmiennej suma. Na końcu zwiększamy wartość zmiennej i o 1.

public static long iterFibonacci(int n) {
	if (n == 0) {
		return 0;
	} else if (n == 1) {
		return 1;
	}
        
long a = 0;
long b = 1;
int i = 2;
    
while (i <= n) {
	long suma = a + b;
	a = b;
	b = suma;
	i = i + 1;
    
	}    
   
}

Po zakończeniu pętli wartość zmiennej b jest zwracana jako wynik działania funkcji.

public static long iterFibonacci(int n) {
	if (n == 0) {
		return 0;
	} else if (n == 1) {
		return 1;
	}
        
long a = 0;
long b = 1;
int i = 2;
    
while (i <= n) {
	long suma = a + b;
	a = b;
	b = suma;
	i = i + 1;
    
	}    

return b;

}

Oto cały kod programu:

public class Main {
	public static void main(String args[]) {
		System.out.println(iterFibonacci(3));
	}

    public static long iterFibonacci(int n) {
        if (n == 0) {
            return 0;
        } else if (n == 1) {
            return 1;
        }
        
        long a = 0;
        long b = 1;
        int i = 2;
        
        while (i <= n) {
            long suma = a + b;
            a = b;
            b = suma;
            i = i + 1;
        }
        return b;
    }
}

Słownik