На этом шаге мы рассмотрим рекурсивную функцию вычисления наибольшего общего делителя.

Один из первых алгоритмов в истории известен как алгоритм Евклида, названный в честь древнегреческого математика Евклида, который описал его в своих "Началах" (прибл. 300 год до н. э.). Его цель - найти наибольший общий делитель (greatest common divisor, gcd), или сокращённо НОД, двух неотрицательных ненулевых целых чисел m и n, то есть наибольшее положительное целое число k, на которое делятся без остатка и m, и n (очевидно, m/k и n/k - целые числа). Например, НОД(20, 24) = 4. Его можно также считать произведением общих простых множителей m и n. Для m = 20 = 2 * 2 * 5 и n = 24 = 2 * 2 * 2 * 3 произведение общих множителей 2 * 2 = 4.

Существует несколько вариантов метода. Первому варианту соответствует следующая функция:

                  n,             если m = 0,
    gcd1(m, n) =  gcd1(n, m),    если m > n,                  (5.2)
                  gcd1(m, n - m) в противном случае,

которую можно закодировать, как показано в примере 5.18.

Пример 5.18. Алгоритм Евклида для вычисления НОД двух неотрицательных целых чисел

1
2
3
4
5
6
7

def gcd1(m, n):
    if m == 0:
        return n
    elif m > n:
        return gcd1(n, m)
    else:
        return gcd1(m, n - m)

Архив с файлом можно взять здесь.

Во-первых, это - функция с хвостовой рекурсией, поскольку её значение определяется вызовом самой себя в рекурсивных условиях. Кроме того, заметьте, что в начальном условии метод возвращает значение аргумента функции, что является обычным для многих рекурсивных хвостовых вызовов. В частности, ясно, что НОД для n > 0 и для 0 - это n, так как и n, и 0 делятся на n без остатка. Первое рекурсивное условие просто меняет местами аргументы. Это гарантирует, что во втором рекурсивном условии первый из них будет не меньше второго. В этом последнем рекурсивном условии уменьшение размера задачи (который зависит от m и n) на 1 или деление его пополам не работает. Вместо этого рекурсивное условие уменьшает второй параметр путём вычитания из него m (отметим, что n - m > 0, так как n > m). Оно реализует математическое свойство

    НОД(m, n) = НОД(m, n - m),   (5.3)

которое не вполне очевидно. Показать его истинность можно следующим образом. Пусть n > m, m = a * z и n = b * z, где a < b и z = НОД(m, n) - произведение общих простых множителей n и m. Это означает, что a и b не содержат общих простых множителей. Кроме того, пусть b = a + c, тогда n и m можно выразить как:

    n = b * z = (a + c) * z = (a₁ * ... * a_k + c₁ * ... * c_t) * z,          (5.4)

    m = (a₁ * ... * a_k) * z,    (5.5)

где a₁, ..., a_k и c₁, ..., c_t - простые делители a и c соответственно. Ключ к доказательству в том, что a и c не имеют общих простых делителей (то есть a_i ≠ c_j), потому что иначе в (5.4) их можно было бы вынести за скобки, предположив, что a и b имеют общие простые делители, а это неверно. Если же a и c не имеют общих простых делителей, то z = НОД(a * z, c * z), и мы можем заключить, что:

    НОД(а * z, b * z) = z = НОД(а * z, c * z) * НОД(m, n) = НОД(m, n - m).

Кроме того, можно показать, что алгоритм гарантирует достижение начального условия, поскольку значения аргументов уменьшаются, пока один из них не станет нулевым. Для m = 20 и n = 24 метод выполняет следующие рекурсивные вызовы:

    gcd1(20, 24) = gcd1(20, 4) = gcd1(4, 20) =
                 = gcd1(4, 16) = gcd1(4, 12) = gcd1(4, 8) =
                 = gcd1(4, 4)  = gcd1(4, 0)  = gcd1(0, 4) = 4.      (5.6)

Так как хвостовые рекурсивные функции не изменяют результаты рекурсивных вызовов, все они возвращают одно и то же значение, которое получается в начальном условии (gcd1(0, 4) = 4). Поэтому хвостовые рекурсивные функции, по сути, определяют отношения между наборами аргументов. Например, в (5.6) все пары (20, 24), (20, 4) и т. д. связаны со значением 4. В заключение приведём более эффективный вариант алгоритма, который используется в настоящее время:

                  n,               если m = 0,
    gcd2(m, n) =                                     (5.7)
                  gcd2(n % m,  m), если m ≠ 0.

Доказательство свойства рекурсивного условия здесь подобно (5.3). Пусть n > m, m = a * z и n = b * z, где z - произведение общих простых делителей n и m и a < b. Это значит, что a и b не имеют общих простых делителей. Кроме того, пусть b = q + r, где q и r - частное и остаток от деления b / a. Ключ этого доказательства в том, что a и r не имеют общих простых делителей, поскольку иначе они были бы простыми делителями b, что невозможно, так как a и b не имеют общих простых делителей. Отсюда z = НОД(r * z, a * z). Таким образом, мы заключаем, что

    НОД(a * z, b * z) = z = НОД(r * z, a * z) * НОД(m, n) = НОД(n % m, m).

На следующем шаге мы приведем решения нескольких задач.

Предыдущий шаг Содержание Следующий шаг