W e‑materiale Algorytm EuklidesaP7OAFYVSiAlgorytm Euklidesa poznaliśmy algorytm służący do znajdowania największego wspólnego dzielnika dwóch liczb. Znamy także iteracyjną realizację tego algorytmu (omówiona ona została w e‑materiale Algorytm Euklidesa w języku C++PRand33dvAlgorytm Euklidesa w języku C++) – tym razem zbadamy podejście rekurencyjne.

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

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

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 zostanie spełniony, funkcja będzie wywoływana rekurencyjnie do momentu, gdy obie wartości nie będą równe. W przypadku gdy wartość a będzie większa od wartości b, funkcja zwróci NWD(a - b, b), a w odwrotnym przypadku NWD(a, b - a).

Jeżeli warunek nie zostanie 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.

Nasza funkcja wygląda następująco:

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

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++

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. Kod wygląda następująco:

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

	return 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