Algorytm Euklidesa rekurencyjnie

Rekurencja: silnia, potęga i algorytm Euklidesa - Algorytmy: zakres rozszerzony (Python)

Wersja z resztą z dzielenia zamienia parę (a, b) na (b, a % b), aż b będzie zerem. Ten sam pomysł zapisany rekurencyjnie: NWD(a, 0) = a, a NWD(a, b) = NWD(b, a % b). Podstawa programowa dla zakresu rozszerzonego wymaga obu wersji algorytmu: iteracyjnej i rekurencyjnej. Porównaj liczbę kroków w obu wersjach.

def gcd(a, b):
    if b == 0:
        return a
    return gcd(b, a % b)


print("NWD(48, 18) =", gcd(48, 18))
print("NWD(1071, 462) =", gcd(1071, 462))

Ładowanie interaktywnego edytora... Jeśli się nie pojawi, włącz JavaScript.

Wszystkie lekcje kursu Algorytmy: zakres rozszerzony·Zaloguj się, aby zapisać postęp na koncie.