W e‑materiale Algorytm EuklidesaP7OAFYVSiAlgorytm Euklidesa poznaliśmy algorytm służący do znajdowania największego wspólnego dzielnika dwóch liczb naturalnych. Wersję iteracyjną Algorytmu Euklidesa w języku Python omówiliśmy w e‑materiale Algorytm Euklidesa w języku JavaPipCcaBjAAlgorytm Euklidesa w języku Java) – tym razem zbadamy podejście rekurencyjne.

Algorytm Euklidesa z odejmowaniem – implementacja algorytmu w języku Java

Zaimplementujmy z użyciem rekurencji algorytm Euklidesa w języku Java.

Nasza funkcja wygląda następująco:

public int NWD(int a, int b) {
    if (a != b) {
		if (a > b) {
            return NWD(a - b, b);
        }
		return NWD(a, b - a);
	}
    
	return a;
}

W funkcji NWDNWDNWD(), która przyjmuje dwie zmienne typu int, użylibyśmy instrukcji warunkowej if, w której warunek będzie taki sam, jak w przypadku pętli while w wykonaniu iteracyjnym, czyli a != b.

Jeżeli warunek jest spełniony, to znaczy a != b, funkcja będzie wywoływana rekurencyjnie. W przypadku gdy wartość a będzie większa od wartości b, funkcja zwróci NWD(a - b, b), a w przeciwnym przypadku NWD(a, b - a). W algorytmie korzystamy z równości NWD(a, b) = NWD(a - b, b) dla a > b lub NWD(a, b) = NWD(a, b - a) dla b > a, które pokazaliśmy w e‑materiale Algorytm EuklidesaP7OAFYVSiAlgorytm Euklidesa.

Jeżeli warunek nie jest spełniony, funkcja zwróci a. Oczywiście mogłaby też zwrócić b – jeżeli warunek nie zostanie spełniony, będzie to oznaczać, że wartość obu zmiennych jest identyczna.

Funkcja kończy swoje działanie po zwróceniu wartości, więc nie musimy stosować instrukcji else.

Algorytm Euklidesa z dzieleniem – implementacja algorytmu w języku C++

Kod wygląda następująco:

public int NWD(int a, int b) {
    if (b != 0) {
        return NWD(b, a % b);
    }
    return a;
}

Zadeklarujemy funkcję NWD() zwracającą typ int. Przyjmie ona parametry a i b – obydwa typu int. W ciele funkcji umieścimy instrukcję warunkową if, której testem logicznym będzie b != 0. Jeżeli zależność zachodzi, funkcja zwróci samą siebie z argumentami b i a % b. W przeciwnym razie funkcja zwróci zmienną a.

Istotne jest, żeby funkcja zwróciła przypadek podstawowyprzypadek podstawowyprzypadek podstawowy w momencie, gdy b przyjmie wartość 0. W innym przypadku w następnym wywołaniu funkcji pojawiłby się argument, który doprowadziłby do wykonania operacji niedozwolonej, czyli szukania reszty z dzielenia przez 0.

Słownik