На этом шаге мы рассмотрим несколько способов реализации такого сложения.

    Эта задача заключается в сложении двух неотрицательных целых чисел a и b без использования обычных арифметических операций, таких как сложение, вычитание, умножение или деление. Вместо этого разрешается лишь увеличивать или уменьшать число на единицу (конечное число раз). Эта простая задача поможет показать, как выбор размера влияет на способ декомпозиции задачи, приводя к разным рекурсивным алгоритмам.

    Согласно представленной в таблице 1 на 20 шаге первый шаг - это определение размера задачи. Поскольку нам разрешено лишь добавлять или вычитать 1 из a и b, разумно считать, что эту простую операцию следует выполнять a + b раз до тех пор, пока не выполнится начальное условие (вскоре мы увидим, что это можно сделать всего лишь за a или b операций). Если мы выбираем в качестве размера задачи a + b, то начальное условие выполняется при a = b = 0, что соответствует экземпляру наименьшего размера. Кроме того, мы должны рассмотреть другие возможные начальные условия, когда результат может быть легко получен без выполнения рекурсивного вызова. Очевидно, что для этой задачи результат равен b при a = 0 и равен a при b = 0. Более того, с такими начальными условиями становится излишним начальное условие для a = 0 и b = 0. Наконец, эти начальные условия гарантируют, что в рекурсивном условии a и b будут положительными.

    На следующем шаге декомпозиции мы можем уменьшить размер задачи на 1. Поскольку в качестве размера задачи выбрано a + b, можно вычитать единицу как из a, так и из b. Рекурсивная схема при уменьшении a была бы такой:

    Если реализуемая функция - f, то очевидно, что f(a, b) = f(a - 1, b) + 1 определяет рекурсивное условие, и его можно выразить математически как:

                b,               если a = 0
    f(a ,b) =   a,               если b = 0            (4.2)
                f(a - l, b) + 1, если a > 0, b > 0. 

    В примере 4.5 приведена реализация функции в Python.

def slow_addition(a, b):
    if a == 0:
        return b
    elif b == 0:
        return a
    else:
        return slow_addition(a - 1, b) + 1    

    Если бы мы выбрали в качестве размера задачи a, в определении функции появились бы те же два начальных условия, а при декомпозиции задачи пришлось бы уменьшать на единицу значение а. Поэтому получающаяся функция была бы точно такой же. С другой стороны, выбрав в качестве размера задачи b, пришлось бы изменить рекурсивное условие на f(a, b) = f(a, b - 1) + 1, поскольку уменьшать придётся b, а не а.

    Функция в примере 4.5 может быть медленной для больших значений а. С другой стороны, если размером задачи считать наименьший входной параметр, то есть min(a, b), то можно создать более эффективный алгоритм. В этом случае два начальных условия f(0, b) = b и f(a, 0) = а соответствуют наименьшим экземплярам задачи (начальное условие f(0, 0) становится лишним). Для рекурсивных условий мы должны найти декомпозицию, гарантирующую уменьшение размера задачи. Первый подход состоит в уменьшении наименьшего входного параметра, чтобы размер подзадачи был min(a, b) - 1. Например, при a < b рекурсивное правило было бы f(a, b) = f(a - 1, b) + 1, а при a ≥ b мы применили бы правило f(a, b) = f(a, b - 1) + 1. Таким образом, математическая функция была бы следующей:

                  b,               если a = 0
                  a,               если b = 0 (и a ≠ 0)
    f(a, b) = 
                  f(a - 1, b) + 1, если a < b (и a ≠ 0, b ≠ 0)
                  f(a, b - 1) + 1, если b ≤ a (и a ≠ 0, b ≠ 0)

def quicker_slow_addition(a, b):
    if a == 0:
        return b
    elif b == 0:
        return a
    elif a < b:
        return quicker_slow_addition(a - 1, b) + 1
    else:
        return quicker_slow_addition(a, b - 1) + 1    

    Вторая идея заключается в уменьшении обоих параметров, и она тоже гарантирует уменьшение размера задачи. В частности, отметим, что min(a - 1, b - 1) = min(a, b) - 1. Для этой декомпозиции рекурсивная схема была бы такой:

    Следовательно, рекурсивным условием для a > 0 и b > 0 будет f(a, b) = f(a - 1, b - 1) + 1 + 1. По условию задачи оно справедливо, если допустить, что увеличение на 1 выполняется постоянное количество раз (в случае f(a - 1, b - 1) - дважды), что не зависит от входных параметров. Соответствующий этому случаю код приведён в примере 4.7.

def quicker_slow_addition_alt(a, b):
    if a == 0:
        return b
    elif b == 0:
        return a
    else:
        return quicker_slow_addition_alt(a - 1, b - 1) + 1 + 1    

    На следующем шаге мы рассмотрим двойную сумму.

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