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 PythonPsWD7mNY0Algorytm Euklidesa w języku Python. Tym razem zbadamy podejście rekurencyjne.

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

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

W funkcji NWDNWDNWD(), która przyjmuje dwie zmienne, 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.

Nasza funkcja wygląda następująco:

def NWD(a, b):
    if a != b:
        if a > b:
            return NWD(a - b, b)
        else:
            return NWD(a, b - a)
    return a

Algorytm Euklidesa z dzieleniem – implementacja algorytmu w języku Python

Zadeklarujemy funkcję NWD(). Przyjmie ona parametry a i b. 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:

def NWD(a, b):
    if b != 0:
        return NWD(b, a % b)
    else:
        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